Изменения

#<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>[[Автоматы с eps-переходами. Eps-замыкание]]</li>#<li>[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]</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></li><li>[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]</li><li>[[ДМП-автоматы и неоднозначность]]</li> </ol>