577
правок
Изменения
Нет описания правки
{{Теорема|statement= Перечисления графов Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.|proof=Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.
}}
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.
По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]].
Таким образом, мы имеем:{{ОпределениеУтверждение|definition statement=Два помеченных графа Пусть дана грамматика <tex>(G_{1}, f_{1})G</tex> и , <tex>L(G_{2}, f_{2}G)= L</tex> '''изоморфны''', если существует изоморфизм между . Тогда следующие задачи неразрешимы:# Содержит ли <tex>G_{1}L</tex> и тандемный повтор.# Содержит ли <tex>G_{2}L</tex>, сохраняющий распределение метокпалиндром.
}}