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

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

Версия 18:06, 2 января 2015

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

Регулярные языки и ДКА

НКА

Минимизация ДКА

Другие свойства конечных автоматов

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

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

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

Алгоритмы разбора

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

МП-автоматы

Теория вычислимости

Разрешимые и перечислимые языки

Вычислительные формализмы

Примеры неразрешимых задач