Изменения

{{ОпределениеТеорема|definition statement= Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|wЗадача о проверке на пустоту пересечения двух КС-грамматик неразрешима.| proof= |x| \}</tex>. }}Например, если Пусть <tex>L A = \{ \varepsilon(G_1, 0010, 011, 010110 G_2) \}</tex>, то <tex>halfmid L(LG_1) = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(cap L)</tex>.{{Определение|definition = Определим <tex>cycle(LG_2)</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L varnothing \}</tex>. }}Например, если Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>L = \overline{ 01, 011 \A}</tex>, то <tex>cycle(L) = \{ 01таким образом показав, 10что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], 011, 110, 101 \}</tex>то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.

{{Утверждение|id = st3|statement =Пусть Для любого экземпляра ПСП <tex>L</tex> {{---}} регулярный язык(x_1, x_2, ... Тогда язык <tex>half(L, x_n)</tex> также регулярен.|proof =Так как и <tex>L</tex> {{---}} регулярный язык(y_1, y_2, то существует допускающий его ДКА и порождающее его регулярное выражение. Оба эти факта могут быть использованы для доказательства утверждения. Мы выберем первый., y_n)<br/tex>Пусть над алфавитом <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex> {{---}} ДКА, допускающий язык можно подобрать символ <tex>L\# \notin \Sigma</tex>. Рассмотрим строку Для каждого экземпляра построим грамматики:* <tex>xG_1 : S \rightarrow aSa \mid a\#a</tex>. Для того, чтобы проверить, что для всех <tex>x a \in half(L)\Sigma</tex>, нам надо убедиться, что существует строка . Тогда <tex>yL(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex> такой же длины, что и где обозначение <tex>xw^R</tex>, которая, будучи сконкатенированной с {{---}} разворот <tex>xw</tex>, даст строку из .* <tex>LG_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex>, то есть если на вход автомату подать для всех <tex>xy</tex>i = 1, то в конце обработки мы окажемся в терминальном состоянии. Предположим2, что автомат, закончив обработку <tex>x\dots n</tex>, находится в состоянии <tex>q_i</tex>, то есть . Тогда <tex>L(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \delta# (q_0, xy_{i_1} y_{i_2} \dots y_{i_m}) = q_i</tex>. Мы должны проверить^R \mid i_1, что существует строка <tex>yi_2, |y| = |x|\dots i_m \in \{ 1,</tex>2, которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>\dots n \}, то есть <tex>m \delta(q_i, y) geqslant 1 \in F}</tex>.Предположим, что мы прошли <tex>n</tex> вершин автоматаЕсли данный экземпляр ПСП имеет решение, то есть <tex>|x| = nL(G_2)</tex>. Обозначим за содержит хотя бы одну строку вида <tex>S_nw\#w^R</tex> множество всех состояний, с которых можно попасть в терминальные за поэтому <tex>n</tex> шагов. Тогда <tex>q_i L(G_1) \in S_n cap L(G_2) \Leftrightarrow x ne \in half(L)</tex>. Если мы сможем отслеживать <tex>S_nvarnothing</tex> , и <tex>q_i</tex>наоборот, если он не имеет решения, то сможем определять, верно ли, что <tex>x \in halfL(LG_2)</tex>. Заметимне содержит строк такого вида, что соответственно <tex>S_0 L(G_1) \cap L(G_2) = \equiv Fvarnothing</tex>. Очевидно  Таким образом мы можем построить свели проблему соответствий Поста к <tex>S_\overline{n+1A}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = \{ q_j \mid \delta(q_j, q_k) \in Qследовательно, q_k \in S_n \}</tex> {{---}} множество состояний, из которых есть переход в какоезадача о проверке на пустоту пересечения двух КС-либо состояние из <tex>S_n</tex> (по единственному символу)грамматик неразрешима.

|id = st4|statement =Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex> {{---}} регулярный язык. Тогда язык следующие задачи неразрешимы:# Содержит ли <tex>cycle(L)</tex> также регулярентандемный повтор.|proof =# Содержит ли <tex>L</tex> палиндром.