О неразрешимых проблемах для КС грамматик.


Если и КС грамматики, то неразрешимыми проблемами являются:
1. Пусто ли пересечение КС языков? То есть , или нет?
2. Является ли КС языком пересечение КС языков? То есть если и КС грамматики и , -КС язык или нет?
3. Является ли КС языком дополнение КС языка? То есть если — КС грамматика, а — дополнение к КС языку, порожденному грамматикой и , то является ли КС грамматикой грамматика ?
4. Тривиален ли КС язык? То есть ?
5. Эквивалентны ли две КС грамматики ~ , то есть совпадают ли языки, ими порождаемые ?
6. Однозначна ли КС грамматика или нет? То есть существует ли единственный вывод в КС грамматике?

ДОКАЗАТЕЛЬСТВО.
A. Если бы проблему пустоты пересечения КС языков можно было бы решить, то можно было бы определить пусто ли пересечение языков и в лемме 1.10. Так как комбинаторная проблема Поста к которой сводится решение данной задачи неразрешима, то и не разрешима проблема пустоты пересечения двух КС языков. Что и требовалось доказать.
B. Пересечение КС языков не обязательно является КС языком, поскольку для КС языков проблема пустоты пересечения КС языков не разрешима (см. пункт А). Следовательно, данная проблема не разрешима. Что и требовалось доказать.
C. Для доказательства пункта 3 теоремы 1.11 предварительно покажем, что объединение двух КС языков есть КС язык.
Пусть заданы две КС грамматики и тогда язык есть объединение языков, порожденных грамматиками и . Язык порождается грамматикой,  где — новая аксиома, то есть.
Обозначим дополнение языка как , где . Из теории множеств известно, что пересечение множеств есть дополнение объединения дополнений этих множеств. В нашем случае языки, порождаемые КС грамматиками – множество строк, тогда пересечение языков есть дополнение объединения дополнений этих языков, то есть . Так как объединение языков разрешимо, то при разрешимости дополнения КС языка мы решаем проблему пустоты пересечения КС языков, которая не разрешима. Следовательно, проблема, указанная в пункте 3 теоремы 1.11 не разрешима. Что и требовалось доказать.
D. Определение тривиальности языка является неразрешимой проблемой так как универсальное множество представимо в виде объединения КС языка и его дополнения . Если бы тривиальность КС языка бала бы разрешима, то разрешима была бы проблема дополнения КС языка. Но это не так, следовательно, проблема тривиальности КС языка не разрешима. Что и требовалось доказать.
E. Эквивалентность грамматик так же является неразрешимой проблемой так как в противном случае была бы разрешима проблема пустоты пересечения КС языков и проблема дополнения КС языков.
F. Доказывается аналогично пункту Е.
Окончание доказательства.

Вывод. 1. Нами найдено, что разрешимыми являются контекстные (неукорачивающие) языки. Следовательно, определение свойств нетривиального языка в общем случае является неразрешимой проблемой.

Пример: Принадлежность строки языку, порожденному грамматикой типа 0, является неразрешимой проблемой.
2. Для каждого типа грамматики существуют свои неразрешимые проблемы, в том числе и для регулярных грамматик.
3. Неразрешимость той или иной проблемы есть следствие придельной общности поставленной задачи, когда ставиться проблема нахождения свойств языка по заранее неизвестной формальной грамматике, его порождающей.
4. Для частных грамматик, то есть грамматик конкретного вида, неразрешимые в общем случае проблемы могут иметь решение. В таком случае решение задачи будет индивидуально для каждой грамматики.
5. Неразрешимость некоторой проблемы в свете вышесказанного означает, что эффективная процедура, будучи построена для каждого конкретного случая, становится неэффективной в общем случае, так как бесконечно сложна из-за счетности множества грамматик каждого типа.