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