Содержит полное и систематическое изложение материала, входящего в учебную программу курса \"Теория конечных автоматов и формальных языков\", изучаемых студентами специальности \"Фундаментальная информатика и информационные технологии\" Института математики, механики и компьютерных наук Южного федерального университета. Последовательно рассматриваются следующие темы: способы задания и распознавания формальных языков, регулярные языки, конечные автоматы, автоматы со спонтанными переходами, свойства регулярных языков, контекстно-свободные языки, нормальные формы контекстно-свободных языков, автоматы с магазинной памятью. Содержит упражнения и варианты индивидуальных заданий. Предназначен для студентов, которые обучаются по программам бакалавриата и магистратуры в области информационных технологий, прикладной математики и программирования.

Введение......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Глава 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Приложения......222Приложение A. Алгоритмы для контекстно-свободных грамматик......222Приложение B. Задание к курсовой работе......230Приложение C. Варианты заданий......233Приложение D. Пример выполнения заданий курсовой работы......242