ISBN 978-5-7883-0506-6

Е.И.ЧИГАРИНА, М.А.ШАМАШОВ

ТЕОРИЯ КОНЕЧНЫХ

АВТОМАТОВ

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

Допущено учебно-методическим советом по прикладной математике и информатике УМО по классическому университетскому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальности и направлению «Прикладная математика и информатика» и по направлению «Информационные технологии»

С А М А Р А

Издательство СГАУ

2007

УДК 004.43(075)

ББК 32.973

Ч586

Инновационная образовательная программа
" Развитие центра компетенции и подготовка
специалистов мирового уровня в области аэрокосмических и геоинформационных технологий"

Рецензенты: д-р техн. наук, проф. А.А.Калентьев,

д-р техн. наук, проф. М.А.Кораблин

Ч586 Чигарина Е.И. Теория конечных автоматов и формальных языков: учеб. пособие / Е.И. Чигарина, М.А.Шамашов. – Самара:
Изд-во Самар. гос. аэрокосм. ун-та, 2007. – 96 с.: ил.

ISBN 978-5-7883-0506-6

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

Пособие ориентировано на студентов очной и заочной форм обучения, изучающих информатику и компьютерные науки, и специалистов, связанных с задачами проектирования системного и прикладного программного обеспечения автоматизированных систем самой различной ориентации. Рекомендуется в качестве учебного пособия для студентов высших учебных заведений, обучающихся по специальностям: 010500 – Прикладная математика и информатика, 010400 – Информационные технологии по курсам «Языки программирования и методы трансляции», «Теория конечных автоматов и формальных языков». и в лаборатории “Открытые системы”

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

ISBN 978-5-7883-0506-6 © Чигарина Е.И., Шамашов М.А., 2007

© Самарский государственный

аэрокосмический университет, 2007

Оглавление

Введение. 4

Глава 1. Языки и грамматики. Обозначения, определения и классификация. 6

1.1 Понятие грамматики языка. Обозначения. 6

1.2. Классификация грамматик по Хомскому. 11

1.3. Техника построения КС - и А - грамматик. 13

1.4. Синтаксические деревья вывода в КС-грамматиках. Представление. 16

А-грамматик в виде графа состояний. Неоднозначность грамматик. 16

1.5. Синтаксический анализ А-языков. 20

Упражнения к первой главе. 25

Глава 2. Распознаватели и автоматы.. 27

Глава 3. Автоматные грамматики и конечные автоматы.. 30

3.1. Автоматные грамматики и конечные автоматы.. 30

3.2. Эквивалентность недетерминированных и детерминированных А-грамматик. 31

Упражнения к третьей главе. 35

Глава 4. Эквивалентные преобразования контекстно-свободных и автоматных грамматик 37

4.1. Декомпозиция правил грамматики. 37

4.2. Исключение тупиковых правил из грамматик. 40

4.3. Обобщенные КС-грамматики и приведение их к удлиняющей. 42

форме. 42

4.4. Устранение левой рекурсии и левая факторизация. 46

Упражнения к четвертой главе. 47

Глава 5. Свойства автоматных и контекстно-свободных языков. 48

5.1. Общий вид цепочек А-языков и КС-языков. 48

5.2. Операции над языками. 52

5.2.1. Операции над КС-языками. 52

5.2.2 Операции над А-языками. 54

5.2.3. Операции над контекстными языками. 59

5.3. Выводы для практики. 60

5.4. Неоднозначность КС-грамматик и языков. 60

Упражнения к пятой главе. 63

Глава 6. Синтаксический анализ КС-языков. 64

6.1.Методы анализа КС-языков. Грамматики предшествования. 64

6.2. Грамматики предшествования Вирта. 66

6.3. Грамматика предшествования Флойда. 68

6.4 Функции предшествования. 69

Упражнения к шестой главе. 71

Глава 7. Введение в семантику. 72

7.1. Польская инверсная запись. 73

7.2. Интерпретация ПОЛИЗа. 74

7.3. Генерирование команд по ПОЛИЗу. 76

7.4. Алгоритм Замельсона и Бауэра перевода выражений в ПОЛИЗ. 78

7.5. Атрибутные грамматики. 81

Упражнения к седьмой главе. 83

Глава 8. Основные фазы компиляции. 84

Заключение. 87

Приложение. 88

Список рекомендуемой литературы.. 94