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