442
правки
Изменения
→Свойства конечных автоматов
[[Категория: Теория формальных языков]]
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
== Автоматы и регулярные языки ==
=== Регулярные языки и ДКА ===
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками]]
*[[Регулярные языки: два определения и их эквивалентность | Регулярные языки: два определения и их эквивалентность, регулярные выражения]]
*[[Детерминированные конечные автоматы]]
*[[Прямое произведение ДКА]]
*[[Простой сопоставитель регулярных выражений]] <tex> \star </tex>
=== НКА ===
*[[Недетерминированные конечные автоматы]]
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]
*[[Автоматы с eps-переходами. Eps-замыкание]]
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
*[[Эквивалентность состояний ДКА]]
*[[Минимизация ДКА, алгоритм за 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>
=== Нормальные формы КС-грамматик ===
*[[Удаление бесполезных символов из грамматики]]
*[[Удаление длинных правил из грамматики]]
*[[Удаление eps-правил из грамматики]]
*[[Удаление цепных правил из грамматики]]
*[[Нормальная форма Хомского]]
*[[Устранение левой рекурсии]]
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
*[[Нормальная форма Куроды]]<tex> ^\star </tex>
=== Алгоритмы разбора ===
*[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
*[[Алгоритм Эрли]]
*[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
=== Опровержение контекстно-свободности языка ===
*[[Лемма о разрастании для КС-грамматик]]
*[[Лемма Огдена]]
*[[Существенно неоднозначные языки]]
*[[Теорема Парика]]<tex> ^\star </tex>
=== МП-автоматы ===
*[[Автоматы с магазинной памятью]]
*[[Детерминированные автоматы с магазинной памятью]]
*[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
*[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>*[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
