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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Регулярные языки и ДКА)
(Опровержение контекстно-свободности языка)
Строка 63: Строка 63:
 
*[[Лемма Огдена]]
 
*[[Лемма Огдена]]
 
*[[Существенно неоднозначные языки]]
 
*[[Существенно неоднозначные языки]]
 +
*[[Теорема Парика]]
  
 
=== МП-автоматы ===
 
=== МП-автоматы ===

Версия 04:01, 29 декабря 2016

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

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

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

НКА

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

Свойства конечных автоматов

Другие автоматы

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

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

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

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

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

МП-автоматы

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

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

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

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