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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Автоматы и регулярные языки)
(Автоматы и регулярные языки)
Строка 19: Строка 19:
 
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
 
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
 
*[[Контексты и синтаксические моноиды]]
 
*[[Контексты и синтаксические моноиды]]
*[[Теорема Майхилла-Нероуда]]
 
  
 
== Контекстно-свободные грамматики ==
 
== Контекстно-свободные грамматики ==

Версия 14:13, 14 января 2014

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

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

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

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

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

МП-автоматы

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

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

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

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