Участник:Dgerasimov/Тикеты по конспектам year2011

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

1. Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
   • Добавить сюда определение гомоморфизма, образа и прообраза в соответствующий раздел, взять их отсюда, оттуда соответственно, удалить их определения и сослаться на этот конспект. Еще лучше — создать
   • В конспекте упоминается "свободный моноид", но не написано что это такое. Надо написать (в конспекте про моноид), и написать про то, какие еще бывают моноиды (кажется, это называется "моноид с порождающими соотношениями", но, может, говорят и "несвободный моноид"), поищите.
   • Добавить английские аналоги терминам
2. Регулярные языки: два определения и их эквивалентность
3. Детерминированные конечные автоматы
4. Недетерминированные конечные автоматы
5. Построение по НКА эквивалентного ДКА, алгоритм Томпсона
6. Автоматы с eps-переходами. Eps-замыкание
7. Теорема Клини (совпадение классов автоматных и регулярных языков)
8. Эквивалентность состояний ДКА
9. Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
10. Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
11. Прямое произведение ДКА
12. Замкнутость регулярных языков относительно различных операций
13. Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
14. Доказательство нерегулярности языков: лемма о разрастании
15. Интерпретация булевых формул с кванторами как игр для двух игроков
16. Решение уравнений в регулярных выражениях
17. Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
18. Контексты и синтаксические моноиды