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

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

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

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

НКА

6. Недетерминированные конечные автоматы
7. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
8. Автоматы с eps-переходами. Eps-замыкание
9. Теорема Клини (совпадение классов автоматных и регулярных языков)
10. Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)

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

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

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

15. Доказательство нерегулярности языков: лемма о разрастании
16. Интерпретация булевых формул с кванторами как игр для двух игроков
17. Решение уравнений в регулярных выражениях
18. Замкнутость регулярных языков относительно различных операций
19. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
20. Контексты и синтаксические моноиды

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

21. Локальные автоматы[math] ^\star [/math]
22. Двусторонний детерминированный конечный автомат[math] ^\star [/math]
23. Квантовые конечные автоматы[math] ^\star [/math]
24. Автоматы Мура и Мили[math] ^\star [/math]
25. Автоматы в современном мире[math] ^\star [/math]