748
правок
Изменения
Нет описания правки
<li>[[Автоматы Мура и Мили]]<tex> ^\star </tex></li>
<li>[[Автоматы в современном мире]]<tex> ^\star </tex></li>
== Контекстно-свободные грамматики ==
=== Базовые понятия о грамматиках ===
<li>[[Формальные грамматики]]
</li><li>[[Иерархия Хомского формальных грамматик]]
</li><li>[[Неукорачивающие и контекстно-зависимые грамматики, эквивалентность]]
</li><li>[[Правоконтекстные грамматики, эквивалентность автоматам]]
</li><li>[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
</li><li>[[Замкнутость КС-языков относительно различных операций]]
</li><li>[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
</li>
=== Нормальные формы КС-грамматик ===
<li>[[Удаление бесполезных символов из грамматики]]
</li><li>[[Удаление длинных правил из грамматики]]
</li><li>[[Удаление eps-правил из грамматики]]
</li><li>[[Удаление цепных правил из грамматики]]
</li><li>[[Нормальная форма Хомского]]
</li><li>[[Устранение левой рекурсии]]
</li><li>[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
</li><li>[[Нормальная форма Куроды]]<tex> ^\star </tex>
</li>
=== Алгоритмы разбора ===
<li>[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
</li><li>[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]]
</li><li>[[Алгоритм Эрли]]
</li><li>[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
</li>
=== Опровержение контекстно-свободности языка ===
</li><li>[[Лемма о разрастании для КС-грамматик]]
</li><li>[[Лемма Огдена]]
</li><li>[[Существенно неоднозначные языки]]
</li><li>[[Теорема Парика]]<tex> ^\star </tex>
</li>
=== МП-автоматы ===
<li>[[Автоматы с магазинной памятью]]
</li><li>[[МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность]]
</li><li>[[Совпадение множества языков МП-автоматов и контекстно-свободных языков]]
</li><li>[[Детерминированные автоматы с магазинной памятью]]
</li><li>[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
</li><li>[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>
</li><li>[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>
</li><li>[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
</li><li>[[ДМП-автоматы и неоднозначность]]</li>
</ol>
