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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Теория Вычислимости)
(Теория Вычислимости)
Строка 53: Строка 53:
 
*[[Разрешимость перечислимого и коперечислимого языка]]
 
*[[Разрешимость перечислимого и коперечислимого языка]]
 
*[[Вычислимые функции]]
 
*[[Вычислимые функции]]
*[[Диагональный метод. Невозможность одновременного существования универсальной функции и всюду определенности]]
+
*[[Диагональный метод. Невозможность одновременного существования универсальной функции и всюду определенности всех элементов семейства вычислимых функций]]
 
*[[Характеристика перечислимых множеств через вычислимые функции]]
 
*[[Характеристика перечислимых множеств через вычислимые функции]]
 
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]
 
*[[Свойства перечислимых языков. Теорема Успенского-Райса]]

Версия 05:01, 29 ноября 2010

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

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

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