Конечные автоматы и формальные языки

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ 
РОССИЙСКОЙ ФЕДЕРАЦИИ 
Федеральное государственное автономное образовательное  
учреждение высшего образования 
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 
 
 
 
                                                                                                                    

 

Е. В. Алымова 
В. М. Деундяк 
А. М. Пеленицын 
 
 
Конечные автоматы  
и формальные языки  

 
 
 
Учебник 
 
 
 
 
 
                                              
 
Ростов-на-Дону – Таганрог 
Издательство Южного федерального университета 
2018 

УДК 004.4'242:519.713(075.8) 
ББК  32.973.26-018.2я73 
         А55 
 
Печатается по решению кафедры алгебры и дискретной математики 
Институт математики, механики и компьютерных наук им. И. И. Воровича 
Южного федерального университета (протокол № 7 от 13 февраля 2017 г.) 
 

Рецензенты: 

профессор кафедры информатики и информационных таможенных технологий 

Ростовского филиала Российской таможенной академии,  

доктор физико-математических наук, доцент О. Е. Кудрявцев; 

 

доцент кафедры «Кибербезопасность информационных систем» Донского  
государственного технического университета, кандидат технических наук, 

 доцент Н. С. Могилевская 

  
 

 
Алымова, Е. В. 
А55 
 
Конечные автоматы и формальные языки : учебник / Е. В. Алымова, В. М. Деундяк, А. М. Пеленицын ; Южный федеральный 
университет. – Ростов-на-Дону ; Таганрог : Издательство Южного 
федерального университета, 2018. – 292 с. 
ISBN  978-5-9275-2397-9 
 
Cодержит полное и систематическое изложение материала, входящего в учебную программу курса «Теория конечных автоматов и формальных языков», изучаемых студентами специальности «Фундаментальная информатика и информационные технологии» Института математики, механики и компьютерных наук Южного 
федерального университета. Последовательно рассматриваются следующие темы: способы задания и распознавания формальных языков, регулярные языки, 
конечные автоматы, автоматы со спонтанными переходами, свойства регулярных 
языков, контекстно-свободные языки, нормальные формы контекстно-свободных 
языков, автоматы с магазинной памятью. Содержит упражнения и варианты индивидуальных заданий. Предназначен для студентов, которые обучаются по программам бакалавриата и магистратуры в области информационных технологий, 
прикладной математики и программирования.  

УДК 004.4'242:519.713(075.8) 
ББК 32.973.26-018.2я73 

 
ISBN  978-5-9275-2397-9 
© Южный федеральный университет, 2018 
© Алымова Е. В., Деундяк В. М.,  
    Пеленицын А. М., 2018 

ОГЛАВЛЕНИЕ

Введение
7

Глава 1. Способы задания и распознавания формальных

языков
12

§ 1.1. Алфавит и слова . . . . . . . . . . . . . . . . . . . . . . . . .
12

§ 1.2. Языки и операции над языками . . . . . . . . . . . . . . .
14

§ 1.3. Грамматики . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19

§ 1.4. Классификация грамматик . . . . . . . . . . . . . . . . . .
26

§ 1.5. Распознаватели
. . . . . . . . . . . . . . . . . . . . . . . . .
28

§ 1.6. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31

Глава 2. Регулярные языки
33

§ 2.1. Регулярные множества и регулярные выражения . . . .
33

§ 2.2. Уравнения и системы уравнений с регулярными коэф
фициентами . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37

§ 2.3. Алгоритм решения систем с регулярными коэффици
ентами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43

§ 2.4. Совпадение классов регулярных и ПЛ-языков . . . . . .
48

Оглавление

§ 2.5. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53

Глава 3. Конечные автоматы
56

§ 3.1. Определения и примеры . . . . . . . . . . . . . . . . . . . .
56

§ 3.2. Редукция НКА к ДКА
. . . . . . . . . . . . . . . . . . . . . .
63

§ 3.3. Граф переходов . . . . . . . . . . . . . . . . . . . . . . . . . .
68

§ 3.4. Совпадение классов КА-, регулярных и ПЛ-языков . . .
69

§ 3.5. Лемма о разрастании для регулярных языков . . . . . .
75

§ 3.6. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78

Глава 4. Конечные автоматы со спонтанными переходами
80

§ 4.1. Определения и примеры . . . . . . . . . . . . . . . . . . . .
80

§ 4.2. Редукция ε-НКА к ДКА . . . . . . . . . . . . . . . . . . . . .
85

§ 4.3. Преобразование регулярного выражения в автомат . .
88

§ 4.4. Построение ε-НКА по ПЛ-грамматике . . . . . . . . . . .
95

§ 4.5. Вычисление языка ε-НКА . . . . . . . . . . . . . . . . . . . 100

§ 4.6. Задача минимизации конечного автомата . . . . . . . . 106

§ 4.7. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

Глава 5. Булева алгебра регулярных языков
125

§ 5.1. Свойства регулярных языков . . . . . . . . . . . . . . . . . 125

§ 5.2. Замкнутость относительно булевых операций . . . . . . 138

§ 5.3. Алгоритмические проблемы регулярных языков . . . . 140

§ 5.4. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

Оглавление
5

Глава 6. Контекстно-свободные языки
145

§ 6.1. Деревья выводов в КС-грамматиках
. . . . . . . . . . . . 145

§ 6.2. Проблема непустоты и устранение бесполезных сим
волов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

§ 6.3. Построение приведенной КС-грамматики
. . . . . . . . 158

§ 6.4. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

Глава 7. Нормальные формы КС-грамматик
168

§ 7.1. Нормальная форма Хомского . . . . . . . . . . . . . . . . . 168

§ 7.2. Проблема принадлежности для КС-языков . . . . . . . . 174

§ 7.3. Матричный метод перехода к нормальной форме

Грейбах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

§ 7.4. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186

Глава 8. Автоматы с магазинной памятью
188

§ 8.1. Определения и примеры . . . . . . . . . . . . . . . . . . . . 188

§ 8.2. Расширенный МП-автомат . . . . . . . . . . . . . . . . . . 196

§ 8.3. Автомат, допускающий слово опустошением магазина 202

§ 8.4. Эквивалентность МП-автоматов и КС-грамматик . . . . 209

§ 8.5. Детерминированный МП-автомат
. . . . . . . . . . . . . 217

§ 8.6. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

Список литературы
220

Оглавление

Приложение A. Алгоритмы
для
контекстно-свободных

грамматик
222

Приложение B. Задание к курсовой работе
230

Приложение C. Варианты заданий
233

Приложение D. Пример выполнения заданий курсовой ра
боты
242

ВВЕДЕНИЕ

В настоящее время в связи с бурным развитием информацион
ных технологий и расширением сферы их применения в теоретиче
ской информатике возникают новые и развиваются старые направ
ления. Всё это находит своё отражение в формировании учебных

дисциплин по направлению «Фундаментальная информатика и ин
формационные технологии».

Целью изучения дисциплины «Теория конечных автоматов и

формальных языков» является выработка у студентов компетенций,

связанных с теоретическими понятиями, идеями, методами, моде
лями, алгоритмами, применяемыми при разработке и сопровожде
нии проблемно-ориентированных языков. Эта дисциплина содер
жит сведения, необходимые для научно-исследовательской и прак
тической работы в области системного программирования, исполь
зования и развития языков программирования.

К основным задачам дисциплины относятся:

- освоение математических основ теории формальных языков;

изучение классов формальных языков и конечных способов за

Введение

дания потенциально бесконечных множеств; овладение мето
дами разбора слов, принадлежащих языку, определения эквива
лентности выводов, установление однозначности грамматик;

- освоение математических основ теории регулярных языков и

выражений; изучение свойств регулярных выражений;

- овладение методами построения регулярных выражений для

языков, заданных неформально и в виде формальных грамма
тик; освоение методов перехода от грамматики к регулярному

выражению и наоборот;

- освоение математических основ теории детерминированных

и недетерминированных конечных автоматов; изучение об
щей схемы автомата-распознавателя; освоение метода редук
ции недетерминированного автомата к детерминированному;

овладение методами построения конечного автомата по регу
лярной грамматике; изучение свойств праволинейных, регу
лярных и автоматных языков;

- освоение понятия конечного автомата со спонтанными перехо
дами; овладение методами построения конечного автомата по

праволинейной грамматике и вычисления языка конечного ав
томата с помощью последовательного исключения состояний;

изучение понятий отношения эквивалентности на множестве

конечных автоматов, недостижимых состояний автомата;

- изучение задачи минимизации детерминированного конечно
го автомата; освоение понятий различимых и неразличимых

состояний и метода построения системы отношений неразли
чимости состояний конечного автомата;

- овладение методами определения регулярности языка; изуче
ние алгоритмических проблем регулярных языков;

- освоение математических основ теории контекстно-свободных

(КС) языков; изучение понятий дерева вывода в КС-грамматике;

овладение методами проверки КС-грамматики на непустоту,

построения по КС-грамматике стабилизационного множества,

построения приведенной КС-грамматики; изучение нормаль
ных форм Хомского и Грейбах КС-языков; освоение метода

определения принадлежности цепочки языку, заданному КС
грамматикой;

- освоение математических основ теории автоматов с магазин
ной памятью (МП-автоматов); изучение понятия недетерми
низма для МП-автоматов, расширенной формы МП-автомата

(РМП-автомат), автомата, допускающего язык опустошением

магазина (МПε-автомат); овладение методами перехода от МП
автомата к МПε-автомату и наоборот;

- овладение
методом
построения
МПε-автомата
по
КС
грамматике; овладение методом перехода от МПε-автомата к

КС-грамматике.

Введение

Исчерпывающее изложение элементов теории формальных

языков и конечных автоматов имеется в ставшей редкостью замеча
тельной монографии А. Ахо и Дж. Ульмана [2], материалы которой

в современной форме представлены в [8]. Настоящий учебник со
держит систематическое изложение значительной части материала

курса «Теория конечных автоматов и формальных языков» в объёме,

достаточном для успешного его освоения. При изложении материа
ла мы пытались придерживаться канонов монографии А. Ахо и Дж.

Ульмана [2], опуская, однако, более глубокие аспекты рассматрива
емой теории, на которые не достает времени в рамках данного кур
са. По курсу «Теория автоматов и формальных языков» можно по
рекомендовать ряд хороших книг, названия некоторых содержатся

в списке литературы.

Учебник состоит из введения, восьми глав, списка литературы и

четырёх приложений. В главе 1 идет речь о способах задания и рас
познавания формальных языков; в главе 2 исследуются регулярные

языки; в главах 3 и 4 изучаются разные типы конечных автоматов

и доказывается совпадение классов конечно-автоматных, регуляр
ных и праволинейных языков; в главе 5 изучается булева алгебра ре
гулярных языков, свойства замкнутости операций над регулярными

множествами и алгоритмические проблемы регулярных языков; в

главах 6 и 7 исследуются контекстно-свободные грамматики и язы
ки; в главе 8 устанавливается связь между контекстно-свободны