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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Разрешимые и перечислимые языки)
(Автоматы и регулярные языки)
Строка 9: Строка 9:
 
*[[Автоматы с eps-переходами. Eps-замыкание]]
 
*[[Автоматы с eps-переходами. Eps-замыкание]]
 
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
 
*[[Теорема Клини (совпадение классов автоматных и регулярных языков)]]
 +
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
 
*[[Замкнутость регулярных языков относительно различных операций]]
 
*[[Замкнутость регулярных языков относительно различных операций]]
 
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
 
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
Строка 14: Строка 15:
 
*[[Доказательство нерегулярности языков: лемма о разрастании]]
 
*[[Доказательство нерегулярности языков: лемма о разрастании]]
 
*[[Решение уравнений в регулярных выражениях]]
 
*[[Решение уравнений в регулярных выражениях]]
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
 
 
*[[Эквивалентность состояний ДКА]]
 
*[[Эквивалентность состояний ДКА]]
 
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
 
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]

Версия 22:04, 1 сентября 2014

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

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

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

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

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

МП-автоматы

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

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

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

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