Московский Государственный Технический Университет им. Н.Э.Баумана

Материалы по курсу
"Основы теории автоматов"

Программа курса (вопросы экзамена)

1. Понятие конечного автомата: состояния автомата, входной алфавит, переходы, начальное и конечные состояния. Диаграмма состояний конечного автомата (диаграмма Мура). Автоматы с полным и неполным набором переходов (источники). Детерминированные и недетерминированные конечные автоматы.
2. Реализация устройств и программирование при помощи конечных автоматов. Наиболее общая модель: действия, совершаемые в момент входа в состояние и при переходе из состояния в состояние. Общая структура программы, использующей автоматный подход, примеры.
3. Язык, задаваемый конечным автоматом (детерминированным или недетерминированным). Модель порождения и модель распознавания цепочек языка с помощью детерминированных и недетерминированных автоматов. Примеры автоматных языков.
4. Лемма о разрастании (лемма о накачке, pumping lemma) для автоматных языков. Примеры ее применения для доказательства того, что конкретный язык не является автоматным.
5. Теорема о совпадении классов языков, задаваемых детерминированными и недетерминированными КА. Алгоритм построения детерминированного конечного автомата, эквивалентного заданному недетерминированному, примеры.
6. Конечные автоматы и конечные разбиения множества всех слов, согласованные с операцией правого умножения; взаимно-однозначное соответствие между конечными автоматами и такими разбиениями.
7. Эквивалентность двух вершин конечного автомата. Минимизация детерминированного конечного автомата путем отождествления эквивалентных вершин. Построение минимального детерминированного конечного автомата непосредственно по языку. Теорема об изоморфизме всех минимальных конечных автоматов, задающих один и тот же автоматный язык.
8. Лемма об ограничении сверху на длину цепочек, используемых для проверки эквивалентности двух вершин детерминированного конечного автомата. Алгоритм минимизации детерминированного конечного автомата.
9. Регулярные языки и регулярные выражения, примеры. Теорема Клини о совпадении классов регулярных и автоматных языков.
10. Алгоритмы проверки эквивалентности конечных автоматов или регулярных выражений.
11. Операции над регулярными языками (пересечение, дополнение, произведение, итерация и т.п.). Проблема вычисления звездной высоты регулярного выражения.
12. Использование программы LEX для создания лексических анализаторов (сканеров) и решения различных задач, связанных с разбиением текста на лексемы, которые можно задать набором регулярных выражений. Примеры.
13. Построение минимального детерминированного конечного автомата для решения задачи контекстного поиска.
14. Конечные автоматы с выходом (конечные преобразователи): модели Мили (Mealy) и Мура (Moore). Примеры применения автоматов с выходом в задачах преобразования текстов. Эквивалентность моделей Мили и Мура: алгоритмы построения автомата Мура по автомату Мили и, обратно, автомата Мили по автомату Мура.
15. Композиция двух автоматов с выходом. Построение автомата с выходом, реализующего композицию двух автоматов.
16. Детерминированные функции конечного веса (ограниченно-детерминированные функции), определение и свойства. Совпадение класса функций конечного веса, принимающих пустое значение на пустом слове, с классом функций, задаваемых конечными автоматами с выходом. Построение автомата Мили по детерминированной функции конечного веса.