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