Изменения

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

32 байта добавлено, 11:14, 10 января 2015

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

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

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

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

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

=== НКА ===

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

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

*[[Алгоритм Бржозовского]]

=== ~~Другие свойства~~ Свойства конечных автоматов ===

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

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

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

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

=== Другие автоматы ===

*[[Локальные автоматы]]

~~=== Абстрактные автоматы ===~~*[[Двусторонний детерминированный конечный автомат]]*[[Квантовый конечный автомат]]

*[[Автоматы Мура и Мили]]

3622

правки