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