Конечные автоматы и формальные языки (350,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

УДК 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

Стр.2

ОГЛАВЛЕНИЕ Введение Глава 1. Способы задания и распознавания формальных языков 7 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

Стр.3

4 Оглавление § 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

Стр.4

Оглавление 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

Стр.5

6 Оглавление Приложение A. Алгоритмы для контекстно-свободных грамматик Приложение B. Задание к курсовой работе Приложение C. Варианты заданий Приложение D. Пример выполнения заданий курсовой работы 222 230 233 242

Стр.6