Введение в теорию формальных грамматик, языков и автоматов

В пособии рассмотрены два основных подхода к описанию синтаксиса формальных языков: порождающий и распознающий. Для формальных грамматик как средства порождающего описания языков приведены основные понятия, их классификация и свойства порождаемых ими языков. Распознающим средством задания языков являются автоматы. Рассмотрены конечные автоматы как распознаватели регулярных языков, автоматы с магазинной памятью как распознаватели КС-языков и машины Тьюринга как распознаватели языков общего вида.Пособие предназначено для бакалавров, обучающихся по направлениям «Программная инженерия», «Математическое обеспечение и администрирование информационных систем» и «Информатика и вычислительная техника».