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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Примеры неразрешимых задач)
м (Примеры неразрешимых задач)
Строка 82: Строка 82:
 
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
 
*[[Примеры неразрешимых задач: проблема соответствий Поста |Проблема соответствий Поста]]
 
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
 
*[[Примеры неразрешимых задач: однозначность грамматики|Однозначность КС-грамматики]]
*[[Неразрешимость задачи об эквивалентности КС-грамматик|Задача об эквивалентности КС-грамматик]]
+
*[[Неразрешимость задачи об эквивалентности КС-грамматик|Эквивалентность КС-грамматик]]
 
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
 
*[[Примеры неразрешимых задач: задача о замощении|Задача о замощении полимино]]
 
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]
 
*[[Примеры неразрешимых задач: задача о выводе в полусистеме Туэ|Задача о выводе в полусистеме Туэ]]

Версия 02:51, 3 января 2014

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

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

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

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

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

МП-автоматы

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

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

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

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