Теория формальных языков — различия между версиями
| Строка 1: | Строка 1: | ||
[[Категория: Теория формальных языков]] | [[Категория: Теория формальных языков]] | ||
| − | == | + | == Автоматы и регулярные языки == |
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов]] | *[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов]] | ||
*[[Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини]] | *[[Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини]] | ||
| Строка 7: | Строка 7: | ||
*[[Недетерминированные конечные автоматы]] | *[[Недетерминированные конечные автоматы]] | ||
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] | *[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]] | ||
| − | |||
| − | |||
*[[Автоматы с eps-переходами. Eps-замыкание]] | *[[Автоматы с eps-переходами. Eps-замыкание]] | ||
*[[Теорема Клини (совпадение классов автоматных и регулярных языков]] | *[[Теорема Клини (совпадение классов автоматных и регулярных языков]] | ||
| Строка 16: | Строка 14: | ||
*[[Замкнутость регулярных языков относительно различных операций]] | *[[Замкнутость регулярных языков относительно различных операций]] | ||
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] | *[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]] | ||
| − | |||
| − | |||
*[[Доказательство нерегулярности языков: лемма о разрастании]] | *[[Доказательство нерегулярности языков: лемма о разрастании]] | ||
*[[Интерпретация булевых формул с кванторами как игр для двух игроков]] | *[[Интерпретация булевых формул с кванторами как игр для двух игроков]] | ||
| Строка 24: | Строка 20: | ||
*[[Контексты и синтаксические моноиды]] | *[[Контексты и синтаксические моноиды]] | ||
| − | == | + | == Контекстно-свободные грамматики == |
*[[Формальные грамматики]] | *[[Формальные грамматики]] | ||
*[[Иерархия Хомского формальных грамматик]] | *[[Иерархия Хомского формальных грамматик]] | ||
| Строка 35: | Строка 31: | ||
*[[Удаление длинных правил из грамматики]] | *[[Удаление длинных правил из грамматики]] | ||
*[[Нормальная форма Хомского]] | *[[Нормальная форма Хомского]] | ||
| + | *[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]] | ||
| + | *[[Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики]] | ||
| + | *[[Алгоритм Эрли]] | ||
| + | *[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]] | ||
| + | *[[Устранение левой рекурсии]] | ||
| + | *[[Приведение грамматики к ослабленной нормальной форме Грейбах]] | ||
Версия 19:30, 13 октября 2010
Автоматы и регулярные языки
- Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов
- Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини
- Регулярные языки: два определения и их эквивалентность
- Детерминированные конечные автоматы
- Недетерминированные конечные автоматы
- Построение по НКА эквивалентного ДКА, алгоритм Томпсона
- Автоматы с eps-переходами. Eps-замыкание
- Теорема Клини (совпадение классов автоматных и регулярных языков
- Эквивалентность состояний ДКА
- Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
- Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
- Замкнутость регулярных языков относительно различных операций
- Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
- Доказательство нерегулярности языков: лемма о разрастании
- Интерпретация булевых формул с кванторами как игр для двух игроков
- Решение уравнений в регулярных выражениях
- Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
- Контексты и синтаксические моноиды
Контекстно-свободные грамматики
- Формальные грамматики
- Иерархия Хомского формальных грамматик
- Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
- Правоконтекстные грамматики, эквивалентность автоматам
- Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
- Удаление бесполезных символов из грамматики
- Удаление eps-правил из грамматики
- Удаление цепных правил из грамматики
- Удаление длинных правил из грамматики
- Нормальная форма Хомского
- Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
- Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
- Алгоритм Эрли
- Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
- Устранение левой рекурсии
- Приведение грамматики к ослабленной нормальной форме Грейбах
