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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Контекстно-свободные грамматики)
(Теория вычислимости)
Строка 88: Строка 88:
 
*[[Неразрешимость исчисления предикатов первого порядка]]
 
*[[Неразрешимость исчисления предикатов первого порядка]]
 
*[[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]
 
*[[Неразрешимость проблемы существования решения диофантова уравления в целых числах]]
 
 
*[[Теорема Райса-Шапиро]]
 
*[[Теорема Райса-Шапиро]]

Версия 00:13, 10 октября 2014

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

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

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

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

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

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

МП-автоматы

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

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

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

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