Теория формальных языков — различия между версиями
(→Контекстно-свободные грамматики) |
|||
| Строка 46: | Строка 46: | ||
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] | *[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]] | ||
*[[Лемма Огдена]] | *[[Лемма Огдена]] | ||
| + | *[[Существенно неоднозначные языки]] | ||
| + | == Теория Вычислимости == | ||
| + | *[[Разрешимые (рекурсивные) языки]] | ||
| + | *[[Перечислимые языки]] | ||
| + | *[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]] | ||
| + | *[[Разрешимость перечислимого и коперечислимого языка]] | ||
| + | *[[Вычислимые функции]] | ||
| + | *[[Диагональный метод. Невозможность одновременного существования универсальной функции и всюду определенности всех элементов семейства вычислимых функций]] | ||
| + | *[[Характеристика перечислимых множеств через вычислимые функции]] | ||
| + | *[[Свойства перечислимых языков. Теорема Успенского-Райса]] | ||
| + | *[[Главные нумерации]] | ||
| + | *[[Неотделимые множества]] | ||
| + | *[[Имунные и простые множества]] | ||
| + | *[[Теорема о рекурсии]] | ||
Версия 04:58, 29 ноября 2010
Автоматы и регулярные языки
- Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов
- Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини
- Регулярные языки: два определения и их эквивалентность
- Детерминированные конечные автоматы
- Недетерминированные конечные автоматы
- Построение по НКА эквивалентного ДКА, алгоритм Томпсона
- Автоматы с eps-переходами. Eps-замыкание
- Теорема Клини (совпадение классов автоматных и регулярных языков
- Эквивалентность состояний ДКА
- Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
- Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
- Замкнутость регулярных языков относительно различных операций
- Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
- Доказательство нерегулярности языков: лемма о разрастании
- Интерпретация булевых формул с кванторами как игр для двух игроков
- Решение уравнений в регулярных выражениях
- Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
- Контексты и синтаксические моноиды
Контекстно-свободные грамматики
- Формальные грамматики
- Иерархия Хомского формальных грамматик
- Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
- Правоконтекстные грамматики, эквивалентность автоматам
- Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
- Удаление бесполезных символов из грамматики
- Удаление eps-правил из грамматики
- Удаление цепных правил из грамматики
- Удаление длинных правил из грамматики
- Нормальная форма Хомского
- Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
- Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
- Алгоритм Эрли
- Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
- Устранение левой рекурсии
- Приведение грамматики к ослабленной нормальной форме Грейбах
- Лемма о разрастании для КС-грамматик
- Автоматы с магазинной памятью
- МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
- Совпадение множества языков МП-автоматов и контекстно-свободных языков
- Детерминированные автоматы с магазинной памятью
- Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
- Нормальная форма ДМП-автомата
- Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
- Лемма Огдена
- Существенно неоднозначные языки
Теория Вычислимости
- Разрешимые (рекурсивные) языки
- Перечислимые языки
- Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
- Разрешимость перечислимого и коперечислимого языка
- Вычислимые функции
- [[Диагональный метод. Невозможность одновременного существования универсальной функции и всюду определенности всех элементов семейства вычислимых функций]]
- Характеристика перечислимых множеств через вычислимые функции
- Свойства перечислимых языков. Теорема Успенского-Райса
- Главные нумерации
- Неотделимые множества
- Имунные и простые множества
- Теорема о рекурсии
