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

Теорема:

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

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

[math]\triangleright[/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]G[/math], [math]L(G) = L[/math]. Тогда следующие задачи неразрешимы: Содержит ли [math]L[/math] тандемный повтор. Содержит ли [math]L[/math] палиндром.