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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства конечных автоматов)
 
Строка 28: Строка 28:
 
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
 
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]
 
*[[Контексты и синтаксические моноиды]]
 
*[[Контексты и синтаксические моноиды]]
 +
*[[Булевые формулы с кванторами как игры для двух игроков]]
 +
 
=== Другие автоматы ===
 
=== Другие автоматы ===
 
*[[Локальные автоматы]]<tex> ^\star </tex>
 
*[[Локальные автоматы]]<tex> ^\star </tex>

Текущая версия на 22:28, 10 марта 2018


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

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

Регулярные языки и ДКА[править]

НКА[править]

Минимизация ДКА[править]

Свойства конечных автоматов[править]

Другие автоматы[править]

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

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

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

Алгоритмы разбора[править]

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

МП-автоматы[править]