577
правок
Изменения
Нет описания правки
{{Теорема|statement= Перечисления графов Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.|proof=Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.
Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики:* <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) =\{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>w^R</tex> {{---}} разворот <tex>w</tex>.* <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> для всех <tex>i = Помеченные графы =1, 2, \dots n</tex>. Тогда <tex>L(G_2) =\{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}</tex>.
}}
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.
}}