== Лекция 1 ==*[[Основные определения: алфавитКонечные автоматы, словорегулярные выражения, язык, конкатенация, свободный моноид слов]]*[[Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини]]*[[Регулярные языки: два определения и их эквивалентность]]*[[Детерминированные конечные автоматы]]*[[Недетерминированные конечные автоматы]]*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] == Лекция 2 ==*[[Автоматы с eps-переходами. Eps-замыкание]]*[[Теорема Клини (совпадение классов автоматных и регулярных языков]]*[[Эквивалентность состояний ДКА]]*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]*[[Замкнутость регулярных языков относительно различных операций]]*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] == Лекция 3 ==*[[Доказательство нерегулярности языков: лемма о разрастании]]*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]*[[Решение уравнений в регулярных выражениях]]*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]*[[Контексты и синтаксические моноиды]]..
