Теория формальных языков:Тикеты

Автоматы и регулярные языки

Регулярные языки и ДКА

1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
2. Регулярные языки: два определения и их эквивалентность, регулярные выражения
3. Детерминированные конечные автоматы
4. Прямое произведение ДКА
5. Простой сопоставитель регулярных выражений [math] \star [/math]

НКА

1. Недетерминированные конечные автоматы
2. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
3. Автоматы с eps-переходами. Eps-замыкание
4. Теорема Клини (совпадение классов автоматных и регулярных языков)
5. Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

Минимизация ДКА

1. Эквивалентность состояний ДКА
2. Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
3. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
4. Алгоритм Бржозовского[math] ^\star [/math]

Свойства конечных автоматов

1. Доказательство нерегулярности языков: лемма о разрастании
2. Интерпретация булевых формул с кванторами как игр для двух игроков
3. Решение уравнений в регулярных выражениях
4. Замкнутость регулярных языков относительно различных операций
5. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
6. Контексты и синтаксические моноиды

Другие автоматы

1. Локальные автоматы[math] ^\star [/math]
2. Двусторонний детерминированный конечный автомат[math] ^\star [/math]
3. Квантовые конечные автоматы[math] ^\star [/math]
4. Автоматы Мура и Мили[math] ^\star [/math]
5. Автоматы в современном мире[math] ^\star [/math]