Изменения

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

Нет изменений в размере, 19:09, 16 октября 2013

→‎Автоматы и регулярные языки: переставил в чуть более естественный порядок

*[[Регулярные языки: два определения и их эквивалентность]]

*[[Детерминированные конечные автоматы]]

*[[Прямое произведение ДКА]]

*[[Недетерминированные конечные автоматы]]

*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]

*[[Автоматы с eps-переходами. Eps-замыкание]]

*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]

*[[Эквивалентность состояний ДКА]]

*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]

*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]

*[[Прямое произведение ДКА]]

*[[Замкнутость регулярных языков относительно различных операций]]

*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]

*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]

*[[Доказательство нерегулярности языков: лемма о разрастании]]

*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]

*[[Решение уравнений в регулярных выражениях]]

*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]

*[[Эквивалентность состояний ДКА]]

*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]

*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]

*[[Контексты и синтаксические моноиды]]

1679

правок