Обсуждение участницы:Анна — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удалено содержимое страницы)
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
 +
{{Теорема
 +
|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>.
 +
 +
Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>, и наоборот, если он не имеет решения, то <tex>L(G_2)</tex> не содержит строк такого вида, соответственно <tex>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|тандемный повтор]].
 +
 +
Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром.
 +
 +
Таким образом, мы имеем:
 +
{{Утверждение
 +
|statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы:
 +
# Содержит ли <tex>L</tex> тандемный повтор.
 +
# Содержит ли <tex>L</tex> палиндром.
 +
}}

Текущая версия на 16:16, 4 января 2017

Теорема:
Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.
Доказательство:
[math]\triangleright[/math]

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

Для любого экземпляра ПСП [math](x_1, x_2, ..., x_n)[/math] и [math](y_1, y_2, ..., y_n)[/math] над алфавитом [math]\Sigma[/math] можно подобрать символ [math]\# \notin \Sigma[/math]. Для каждого экземпляра построим грамматики:

  • [math]G_1 : S \rightarrow aSa \mid a\#a[/math] для всех [math]a \in \Sigma[/math]. Тогда [math]L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}[/math], где обозначение [math]w^R[/math] — разворот [math]w[/math].
  • [math]G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i[/math] для всех [math]i = 1, 2, \dots n[/math]. Тогда [math]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 \}[/math].

Если данный экземпляр ПСП имеет решение, то [math]L(G_2)[/math] содержит хотя бы одну строку вида [math]w\#w^R[/math], поэтому [math]L(G_1) \cap L(G_2) \ne \varnothing[/math], и наоборот, если он не имеет решения, то [math]L(G_2)[/math] не содержит строк такого вида, соответственно [math]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]G[/math], [math]L(G) = L[/math]. Тогда следующие задачи неразрешимы:
  1. Содержит ли [math]L[/math] тандемный повтор.
  2. Содержит ли [math]L[/math] палиндром.