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

Материал из Викиконспекты
Перейти к: навигация, поиск
(МП-автоматы)
(Примеры неразрешимых задач)
Строка 116: Строка 116:
 
*[[Неразрешимость исчисления предикатов первого порядка]]
 
*[[Неразрешимость исчисления предикатов первого порядка]]
 
*[[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
 
*[[Неразрешимость проблемы существования решения диофантова уравнения в целых числах]]
 +
*[[Неразрешимость задачи о замощении плоскости набором плиток Вана]]
 
*[[Игра «Жизнь»]]<tex>^\star</tex>
 
*[[Игра «Жизнь»]]<tex>^\star</tex>
 
*[[Неразрешимость игры Braid]]<tex>^\star</tex>
 
*[[Неразрешимость игры Braid]]<tex>^\star</tex>
 
*[[Теорема Райса-Шапиро]]
 
*[[Теорема Райса-Шапиро]]

Версия 10:28, 17 января 2017

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

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

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

НКА

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

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

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

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

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

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

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

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

МП-автоматы

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

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

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

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