Обсуждение участницы:Анна

Теорема:

Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.

Доказательство:

[math]\triangleright[/math]

Пусть [math]A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}[/math]. Сведем проблему соответствий Поста к [math]\overline{A}[/math], таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки замкнуты относительно дополнения, то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.

[math]\triangleleft[/math]

Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.

По двум КС-грамматикам [math]G_1[/math] и [math]G_2[/math] можно построить КС-грамматику для конкатенации задаваемых ими языков [math]L(G_1)L(G_2)[/math]. По аналогии с этим мы можем рассматривать язык [math]L(G_1)\#L(G_2)\#[/math], где [math]\#[/math] — новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть [math]L(G_1) \cap L(G_2) \ne \varnothing [/math], тогда и только тогда, когда [math]L(G_1)\#L(G_2)\#[/math] содержит тандемный повтор.

Аналогично можно заметить, что пересечение [math]L(G_1) \cap L(G_2) \ne \varnothing [/math] тогда и только тогда, когда [math]L(G_1)\#L(G_2)^R[/math] содержит палиндром, где обозначение [math]L^R[/math] — разворот [math]L[/math].

Таким образом, мы имеем:

Утверждение:

Пусть дана грамматика [math]G[/math], [math]L(G) = L[/math]. Тогда следующие задачи неразрешимы: Содержит ли [math]L[/math] тандемный повтор. Содержит ли [math]L[/math] палиндром.