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

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

Версия 21:31, 4 января 2017

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

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

Регулярные языки и ДКА

НКА

Минимизация ДКА

Свойства конечных автоматов

Другие автоматы

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

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

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

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

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

МП-автоматы

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

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

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

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