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

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

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

    см. 1

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