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

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

Версия 00:54, 20 января 2013

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

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

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

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

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

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