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