Теория формальных языков — различия между версиями
Shersh (обсуждение | вклад) м |
Shersh (обсуждение | вклад) |
||
| Строка 12: | Строка 12: | ||
*[[Автоматы с eps-переходами. Eps-замыкание]] | *[[Автоматы с eps-переходами. Eps-замыкание]] | ||
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]] | *[[Теорема Клини (совпадение классов автоматных и регулярных языков)]] | ||
| − | *[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] | + | *[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]<tex> ^\star </tex> |
=== Минимизация ДКА === | === Минимизация ДКА === | ||
*[[Эквивалентность состояний ДКА]] | *[[Эквивалентность состояний ДКА]] | ||
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] | *[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]] | ||
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] | *[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]] | ||
| − | *[[Алгоритм Бржозовского]] | + | *[[Алгоритм Бржозовского]]<tex> ^\star </tex> |
=== Свойства конечных автоматов === | === Свойства конечных автоматов === | ||
*[[Доказательство нерегулярности языков: лемма о разрастании]] | *[[Доказательство нерегулярности языков: лемма о разрастании]] | ||
| Строка 26: | Строка 26: | ||
*[[Контексты и синтаксические моноиды]] | *[[Контексты и синтаксические моноиды]] | ||
=== Другие автоматы === | === Другие автоматы === | ||
| − | *[[Локальные автоматы]] | + | *[[Локальные автоматы]]<tex> ^\star </tex> |
| − | *[[Двусторонний детерминированный конечный автомат]] | + | *[[Двусторонний детерминированный конечный автомат]]<tex> ^\star </tex> |
| − | *[[Квантовые конечные автоматы]] | + | *[[Квантовые конечные автоматы]]<tex> ^\star </tex> |
| − | *[[Автоматы Мура и Мили]] | + | *[[Автоматы Мура и Мили]]<tex> ^\star </tex> |
== Контекстно-свободные грамматики == | == Контекстно-свободные грамматики == | ||
| Строка 39: | Строка 39: | ||
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] | *[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]] | ||
*[[Замкнутость КС-языков относительно различных операций]] | *[[Замкнутость КС-языков относительно различных операций]] | ||
| − | *[[Регулярная аппроксимация КС-языков]] | + | *[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex> |
=== Нормальные формы КС-грамматик === | === Нормальные формы КС-грамматик === | ||
*[[Удаление бесполезных символов из грамматики]] | *[[Удаление бесполезных символов из грамматики]] | ||
| Строка 48: | Строка 48: | ||
*[[Устранение левой рекурсии]] | *[[Устранение левой рекурсии]] | ||
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]] | *[[Приведение грамматики к ослабленной нормальной форме Грейбах]] | ||
| − | *[[Нормальная форма Куроды]] | + | *[[Нормальная форма Куроды]]<tex> ^\star </tex> |
=== Алгоритмы разбора === | === Алгоритмы разбора === | ||
| Строка 81: | Строка 81: | ||
*[[Иммунные и простые множества]] | *[[Иммунные и простые множества]] | ||
*[[Теорема о рекурсии]] | *[[Теорема о рекурсии]] | ||
| − | *[[Квайны]] | + | *[[Квайны]]<tex> ^\star </tex> |
*[[Busy beaver]] | *[[Busy beaver]] | ||
| − | *[[Колмогоровская сложность]] | + | *[[Колмогоровская сложность]]<tex> ^\star </tex> |
=== Вычислительные формализмы === | === Вычислительные формализмы === | ||
*[[Машина Тьюринга]] | *[[Машина Тьюринга]] | ||
| − | *[[Лямбда-исчисление]] | + | *[[Лямбда-исчисление]]<tex> ^\star </tex> |
| − | *[[Примитивно рекурсивные функции]] | + | *[[Примитивно рекурсивные функции]]<tex> ^\star </tex> |
| − | *[[Частично рекурсивные функции]] | + | *[[Частично рекурсивные функции]]<tex> ^\star </tex> |
*[[Стековые машины, эквивалентность двухстековой машины МТ]] | *[[Стековые машины, эквивалентность двухстековой машины МТ]] | ||
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] | *[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]] | ||
| Строка 95: | Строка 95: | ||
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]] | *[[Возможность порождения формальной грамматикой произвольного перечислимого языка]] | ||
*[[Линейный ограниченный автомат]] | *[[Линейный ограниченный автомат]] | ||
| − | *[[Сверхтьюринговые вычисления (гипервычисления)]] | + | *[[Сверхтьюринговые вычисления (гипервычисления)]]<tex> ^\star </tex> |
=== Примеры неразрешимых задач === | === Примеры неразрешимых задач === | ||
Версия 14:50, 11 января 2015
Символом будут помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены в рамках курса.
Автоматы и регулярные языки
Регулярные языки и ДКА
- Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками
- Регулярные языки: два определения и их эквивалентность, регулярные выражения
- Детерминированные конечные автоматы
- Прямое произведение ДКА
НКА
- Недетерминированные конечные автоматы
- Построение по НКА эквивалентного ДКА, алгоритм Томпсона
- Автоматы с eps-переходами. Eps-замыкание
- Теорема Клини (совпадение классов автоматных и регулярных языков)
- Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)
Минимизация ДКА
- Эквивалентность состояний ДКА
- Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний
- Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))
- Алгоритм Бржозовского
Свойства конечных автоматов
- Доказательство нерегулярности языков: лемма о разрастании
- Интерпретация булевых формул с кванторами как игр для двух игроков
- Решение уравнений в регулярных выражениях
- Замкнутость регулярных языков относительно различных операций
- Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
- Контексты и синтаксические моноиды
Другие автоматы
- Локальные автоматы
- Двусторонний детерминированный конечный автомат
- Квантовые конечные автоматы
- Автоматы Мура и Мили
Контекстно-свободные грамматики
Базовые понятия о грамматиках
- Формальные грамматики
- Иерархия Хомского формальных грамматик
- Неукорачивающие и контекстно-зависимые грамматики, эквивалентность
- Правоконтекстные грамматики, эквивалентность автоматам
- Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора
- Замкнутость КС-языков относительно различных операций
- Регулярная аппроксимация КС-языков
Нормальные формы КС-грамматик
- Удаление бесполезных символов из грамматики
- Удаление длинных правил из грамматики
- Удаление eps-правил из грамматики
- Удаление цепных правил из грамматики
- Нормальная форма Хомского
- Устранение левой рекурсии
- Приведение грамматики к ослабленной нормальной форме Грейбах
- Нормальная форма Куроды
Алгоритмы разбора
- Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ
- Алгоритм Кока-Янгера-Касами, модификация для произвольной грамматики
- Алгоритм Эрли
- Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики
Опровержение контекстно-свободности языка
МП-автоматы
- Автоматы с магазинной памятью
- МП-автоматы, допуск по пустому стеку и по допускающему состоянию, эквивалентность
- Совпадение множества языков МП-автоматов и контекстно-свободных языков
- Детерминированные автоматы с магазинной памятью
- Детерминированные автоматы с магазинной памятью, допуск по пустому стеку
- Нормальная форма ДМП-автомата
- Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами
- ДМП-автоматы и неоднозначность
Теория вычислимости
Разрешимые и перечислимые языки
- Разрешимые (рекурсивные) языки
- Перечислимые языки
- Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций
- Вычислимые функции
- Вычислимые числа
- Универсальная функция и главные нумерации
- Свойства перечислимых языков. Теорема Успенского-Райса
- Неотделимые множества
- Иммунные и простые множества
- Теорема о рекурсии
- Квайны
- Busy beaver
- Колмогоровская сложность
Вычислительные формализмы
- Машина Тьюринга
- Лямбда-исчисление
- Примитивно рекурсивные функции
- Частично рекурсивные функции
- Стековые машины, эквивалентность двухстековой машины МТ
- Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ
- Линейный клеточный автомат, эквивалентность МТ
- Возможность порождения формальной грамматикой произвольного перечислимого языка
- Линейный ограниченный автомат
- Сверхтьюринговые вычисления (гипервычисления)
Примеры неразрешимых задач
- m-сводимость
- Проблема соответствий Поста
- Однозначность КС-грамматики
- Эквивалентность КС-грамматик
- Задача о замощении полимино
- Задача о выводе в полусистеме Туэ
- Неразрешимость исчисления предикатов первого порядка
- Неразрешимость проблемы существования решения диофантова уравнения в целых числах
- Теорема Райса-Шапиро
