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

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

Версия 05:22, 18 ноября 2014

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

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

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

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

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

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

МП-автоматы

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

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

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

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