Теория формальных языков — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры неразрешимых задач)
(Регулярные языки и ДКА)
 
(не показаны 54 промежуточные версии 26 участников)
Строка 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>
  
 
== Контекстно-свободные грамматики ==
 
== Контекстно-свободные грамматики ==
 +
=== Базовые понятия о грамматиках ===
 
*[[Формальные грамматики]]
 
*[[Формальные грамматики]]
 
*[[Иерархия Хомского формальных грамматик]]
 
*[[Иерархия Хомского формальных грамматик]]
Строка 27: Строка 46:
 
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
 
*[[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора]]
 
*[[Замкнутость КС-языков относительно различных операций]]
 
*[[Замкнутость КС-языков относительно различных операций]]
 +
*[[Регулярная аппроксимация КС-языков]]<tex> ^\star </tex>
 +
 
=== Нормальные формы КС-грамматик ===
 
=== Нормальные формы КС-грамматик ===
 
*[[Удаление бесполезных символов из грамматики]]
 
*[[Удаление бесполезных символов из грамматики]]
 +
*[[Удаление длинных правил из грамматики]]
 
*[[Удаление eps-правил из грамматики]]
 
*[[Удаление eps-правил из грамматики]]
 
*[[Удаление цепных правил из грамматики]]
 
*[[Удаление цепных правил из грамматики]]
*[[Удаление длинных правил из грамматики]]
 
 
*[[Нормальная форма Хомского]]
 
*[[Нормальная форма Хомского]]
 
*[[Устранение левой рекурсии]]
 
*[[Устранение левой рекурсии]]
 
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
 
*[[Приведение грамматики к ослабленной нормальной форме Грейбах]]
 +
*[[Нормальная форма Куроды]]<tex> ^\star </tex>
 +
 
=== Алгоритмы разбора ===
 
=== Алгоритмы разбора ===
 
*[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
 
*[[Алгоритм Кока-Янгера-Касами разбора грамматики в НФХ]]
Строка 40: Строка 63:
 
*[[Алгоритм Эрли]]
 
*[[Алгоритм Эрли]]
 
*[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
 
*[[Алгоритм Эрли, доказательство оценки O(n^2) для однозначной грамматики]]
 +
 
=== Опровержение контекстно-свободности языка ===
 
=== Опровержение контекстно-свободности языка ===
 
*[[Лемма о разрастании для КС-грамматик]]
 
*[[Лемма о разрастании для КС-грамматик]]
 
*[[Лемма Огдена]]
 
*[[Лемма Огдена]]
 
*[[Существенно неоднозначные языки]]
 
*[[Существенно неоднозначные языки]]
 +
*[[Теорема Парика]]<tex> ^\star </tex>
 +
 
=== МП-автоматы ===
 
=== МП-автоматы ===
 
*[[Автоматы с магазинной памятью]]
 
*[[Автоматы с магазинной памятью]]
Строка 50: Строка 76:
 
*[[Детерминированные автоматы с магазинной памятью]]
 
*[[Детерминированные автоматы с магазинной памятью]]
 
*[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
 
*[[Детерминированные автоматы с магазинной памятью, допуск по пустому стеку]]
*[[Нормальная форма ДМП-автомата]]
+
*[[Нормальная форма ДМП-автомата]]<tex> ^\star </tex>
 +
*[[Эквивалентность ДМП-автоматов]]<tex> ^\star </tex>
 
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 
*[[Несовпадение класса языков, распознаваемых ДМП автоматами и произвольными МП автоматами]]
 
+
*[[ДМП-автоматы и неоднозначность]]
== Теория вычислимости ==
 
=== Разрешимые и перечислимые языки ===
 
*[[Разрешимые (рекурсивные) языки]]
 
*[[Перечислимые языки]]
 
*[[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций]]
 
*[[Вычислимые функции]]
 
*[[Вычислимые числа]]
 
*[[Диагональный метод]]
 
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]
 
*[[Главные нумерации]]
 
*[[Неотделимые множества]]
 
*[[Иммунные и простые множества]]
 
*[[Теорема о рекурсии]]
 
*[[Busy beaver]]
 
 
 
=== Вычислительные формализмы ===
 
*[[Машина Тьюринга]]
 
*[[Лямбда-исчисление]]
 
*[[Примитивно рекурсивные функции]]
 
*[[Частично рекурсивные функции]]
 
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
 
*[[Счетчиковые машины, эквивалентность двухсчетчиковой машины МТ]]
 
*[[Линейный клеточный автомат, эквивалентность МТ]]
 
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
 
 
 
=== Примеры неразрешимых задач ===
 
*[[m-сводимость]]
 
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
 
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
 
*[[Неразрешимость задачи об эквивалентности КС-грамматик|Задача об эквивалентности КС-грамматик]]
 
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
 
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
 
*[[Неразрешимость исчисления предикатов первого порядка]]
 
*[[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]
 
 
 
*[[Теорема Райса-Шапиро]]
 

Текущая версия на 13:46, 8 января 2021


Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

Автоматы и регулярные языки[править]

Регулярные языки и ДКА[править]

НКА[править]

Минимизация ДКА[править]

Свойства конечных автоматов[править]

Другие автоматы[править]

Контекстно-свободные грамматики[править]

Базовые понятия о грамматиках[править]

Нормальные формы КС-грамматик[править]

Алгоритмы разбора[править]

Опровержение контекстно-свободности языка[править]

МП-автоматы[править]