3622
правки
Изменения
Нет описания правки
*[[Автоматы с eps-переходами. Eps-замыкание]]
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]<tex> ^\star </tex>
=== Минимизация ДКА ===
*[[Эквивалентность состояний ДКА]]
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
*[[Алгоритм Бржозовского]]<tex> ^\star </tex>
=== Свойства конечных автоматов ===
*[[Доказательство нерегулярности языков: лемма о разрастании]]
*[[Контексты и синтаксические моноиды]]
=== Другие автоматы ===
*[[Локальные автоматы]]<tex> ^\star </tex>*[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex>*[[Квантовые конечные автоматы]]<tex> ^\star </tex>*[[Автоматы Мура и Мили]]<tex> ^\star </tex>
== Контекстно-свободные грамматики ==
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
*[[Замкнутость КС-языков относительно различных операций]]
*[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
=== Нормальные формы КС-грамматик ===
*[[Удаление бесполезных символов из грамматики]]
*[[Устранение левой рекурсии]]
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
*[[Нормальная форма Куроды]]<tex> ^\star </tex>
=== Алгоритмы разбора ===
*[[Иммунные и простые множества]]
*[[Теорема о рекурсии]]
*[[Квайны]]<tex> ^\star </tex>
*[[Busy beaver]]
*[[Колмогоровская сложность]]<tex> ^\star </tex>
=== Вычислительные формализмы ===
*[[Машина Тьюринга]]
*[[Лямбда-исчисление]]<tex> ^\star </tex>*[[Примитивно рекурсивные функции]]<tex> ^\star </tex>*[[Частично рекурсивные функции]]<tex> ^\star </tex>
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
*[[Линейный ограниченный автомат]]
*[[Сверхтьюринговые вычисления (гипервычисления)]]<tex> ^\star </tex>
=== Примеры неразрешимых задач ===
