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