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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теория вычислимости)
м (Вычислительные формализмы)
Строка 61: Строка 61:
 
=== Вычислительные формализмы ===
 
=== Вычислительные формализмы ===
 
*[[Машина Тьюринга]]
 
*[[Машина Тьюринга]]
 +
*[[Императивные языки программирования]]
 
*[[Лямбда-исчисление]]
 
*[[Лямбда-исчисление]]
 
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
 
*[[Стековые машины, эквивалентность двухстековой машины МТ]]
Строка 66: Строка 67:
 
*[[Линейный клеточный автомат, эквивалентность МТ]]
 
*[[Линейный клеточный автомат, эквивалентность МТ]]
 
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
 
*[[Возможность порождения формальной грамматикой произвольного перечислимого языка]]
 +
 
=== Примеры неразрешимых задач ===
 
=== Примеры неразрешимых задач ===
 
*[[m-сводимость]]
 
*[[m-сводимость]]

Версия 18:48, 13 декабря 2012

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

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

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

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

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

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