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

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

 

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

 
 
 
Учебник 
 
 
 
 
 
                                              
 
Ростов-на-Дону – Таганрог 
Издательство Южного федерального университета 
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 устанавливается связь между контекстно-свободны

ми языками и конечными автоматами с магазинной памятью. Каж
дая глава снабжена набором упражнений для лучшего понимания

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

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

одного варианта курсовой работы.

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

освоение материала курсов математическая логики и теории алго
ритмов.

Нумерация всех утверждений имеет вид: α.β.γ, где α — номер

главы, β — номер раздела главы, γ — номер утверждения в разделе.

Формулировки теорем, лемм и утверждений заканчиваются симво
лом ◻, а доказательства заканчиваются символом ∎. Формулировки

упражнений заканчиваются символом ◻, а окончания примеров по
мечаются символом ∎.

В тексте не выделяются и не нумеруются определения, однако

некоторые важные понятия, появляющиеся по ходу изложения, на
браны курсивом.

О всех найденных в тексте ошибках и опечатках следует сооб
щать по адресу электронной почты a.pelenitsyn@gmail.com.

ГЛАВА 1

СПОСОБЫ ЗАДАНИЯ И РАСПОЗНАВАНИЯ

ФОРМАЛЬНЫХ ЯЗЫКОВ

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

Алфавитом будем называть любое множество символов. Пред
полагается, что термин «символ» имеет достаточно ясный интуи
тивный смысл и не нуждается в дальнейшем пояснении. Алфавит,

вообще говоря, не обязан быть ни конечным, ни даже счетным, но

везде далее мы будем предполагать его конечным. Термины «буква»

и «знак» используются как синонимы термина «символ» для обозна
чения элемента алфавита. Термин «буква» будет для нас основным.

Если написать последовательность букв алфавита Σ, располагая

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

1.1. Алфавит и слова
13

Слово называется пустым, если оно не содержит ни одной бук
вы. Это слово обозначается символом ε.

Пример 1.1.1. Латинский алфавит: множество, состоящее из 26

прописных и 26 строчных латинских букв; begin — слово в этом ал
фавите.
∎

Пример 1.1.2. Бинарный (или двоичный) алфавит: множество

(0; 1); 001001 — слово в этом алфавите.
∎

Определим две операции над словами:

1) Если α и β — слова, то слово αβ называется конкатенацией

(сцеплением) α и β. Например, если α = вино, β = град, то

αβ = виноград. Для любого слова α всегда αε = εα = α.

2) Обращением слова α называется слово αR, которое отличается от

α только порядком следования входящих в него букв, т.е. если a1,

a2, ..., an — буквы и α = a1 . . . an, то αR = an . . . a1. Ясно, что εR = ε.

Например, если α = нос, то αR = сон.

Пусть α, β и γ — произвольные слова в некотором алфавите Σ.

Назовем α префиксом слова αβ, а β — суффиксом слова αβ. Слово β

назовем подсловом слова αβγ. Префикс и суффикс являются подсло
вами. Заметим, что пустое слово является префиксом, суффиксом и

подсловом любого слова. Если α ≠ β и α — префикс слова β, то α назы
вается собственным префиксом слова β; аналогично определяются

собственные суффиксы и подслова.

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

Слова вида aa...a (n букв) будем записывать короче: an. Напри
мер:

aabbba = a2b3a,
ε = a0.

Длиной слова будем называть число букв в нем. Длину слова α

будем обозначать ∣α∣. Например, ∣aab∣ = 3, ∣ε∣ = 0.

Упражнение 1.1.1. Выясните, сколько букв в русском алфавите. ◻

Упражнение 1.1.2. Найдите все префиксы, суффиксы и подслова

слова арбуз.
◻

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

Языком над алфавитом Σ называется произвольное множество

слов, записанных буквами из Σ. Под это определение, конечно, под
ходит почти любое известное понятие языка. Например, англий
ский и русский языки, различные алгоритмические языки и т. д.

Рассмотрим простейшие примеры языков над некоторым алфа
витом Σ:

- пустое множество ∅;

- множество {ε}, состоящее из одного пустого слова;

- множество {a}, где a ∈ Σ, состоящее из одного однобуквенного

слова.