Изменения

{{ОпределениеТеорема|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> {{---}} регулярный язык. Тогда язык Для любого экземпляра ПСП <tex>half(L)</tex> также регулярен.|proof =Так как <tex>L</tex> {{---}} регулярный языкx_1, то существует ДКА <tex>M = \langle \Sigma x_2, Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить., что <tex>x \in half(Lx_n)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>(y_1, котораяy_2, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим.., что автомат, закончив обработку <tex>xy_n)</tex>, находится в состоянии над алфавитом <tex>q_i\Sigma</tex>, то есть можно подобрать символ <tex>\delta(q_0, x) = q_i</tex>. Мы должны проверить, что существует строка <tex>y, |y| = |x|,</tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex># \delta(q_i, y) notin \in FSigma</tex>.<br>Для каждого экземпляра построим грамматики:Предположим, что мы прошли * <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i G_1 : S \in S_n rightarrow aSa \Leftrightarrow x mid a\in half(L)#a</tex>. Если мы сможем отслеживать для всех <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x a \in half(L)</tex>. Заметим, что <tex>S_0 \equiv FSigma</tex>. Очевидно мы можем построить Тогда <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prevL(S_nG_1) = \{ q w\in Q #w^R \mid \exists a w \in \Sigma, q' \in S_n, \delta(q, a) = q' ^* \}</tex> {{---}} множество состояний, из которых есть переход в какое-либо состояние из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и обновлять где обозначение <tex>S_n</tex>.<br>Построим ДКА <tex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2w^Q</tex>, то есть каждое состояние <tex>M'R</tex> {{---}} это пара из одиночного состояния из разворот <tex>M</tex> и множества состояний из <tex>Mw</tex>. Функцию перехода * <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\delta'#y^R_i</tex> автомата для всех <tex>M'</tex> определим такi = 1, 2, чтобы если по какой-то строке <tex>x</tex> длины <tex>\dots n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние . Тогда <tex>L(q_i, S_nG_2)</tex>, где <tex>S_n</tex> = \{x_{---i_1}x_{i_2} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_\dots x_{n+1i_m}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev# (S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний y_{i_1} y_{---i_2}} <tex>F' = \dots y_{ (q, Si_m}) ^R \mid q i_1, i_2, \dots i_m \in S\{ 1, 2, \dots n \}, S m \in 2^Q geqslant 1 \}</tex>.<br>Теперь по индукции не сложно доказатьЕсли данный экземпляр ПСП имеет решение, что то <tex>\delta'L(q_0', x) = (\delta(q_0, x), S_nG_2)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает содержит хотя бы одну строку вида <tex>xw\#w^R</tex> тогда и только тогда, когда поэтому <tex>L(G_1) \deltacap L(q_0, xG_2) \in S_nne \varnothing</tex>. Следовательно, автомат и наоборот, если он не имеет решения, то <tex>M'L(G_2)</tex> допускает язык не содержит строк такого вида, соответственно <tex>halfL(G_1) \cap L(G_2)= \varnothing</tex>. Таким образом, мы построили ДКА, который допускает язык свели проблему соответствий Поста к <tex>half(L)\overline{A}</tex>. Следовательно, данный язык является регулярнымследовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.

|id = st4|statement =Пусть дана грамматика <tex>LG</tex> {{---}} регулярный язык. Тогда язык , <tex>cycleL(G) = L)</tex> также регулярен.|proof =[[ФайлТогда следующие задачи неразрешимы:Enfa_before.jpg|left|thumb|240px|Рис. 1. Разбиение автомата.]][[Файл:Enfa-after.jpg|right|thumb|240px|Рис. 2. Перестроение.]]Так как # Содержит ли <tex>L</tex> {{---}} регулярный язык, то существует допускающий его ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>тандемный повтор. Построим из <tex>M</tex> недетерминированный автомат с <tex>\varepsilon-</tex>переходами следующим образом: рассмотрим состояние <tex>q \in Q</tex>, из которого есть переходы в другие состояния (то есть начиная с <tex>q</tex> можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с <tex>q</tex>, станет префиксом нового слова, а префикс, заканчивающийся в <tex>q</tex> {{---}} суффиксом. Разделим автомат на две части <tex>A_1</tex> и <tex>A_2</tex> такие, что <tex>A_1</tex> будет содержать все вершины, из которых достижима <tex>q</tex>, а <tex>A_2</tex> {{---}} все вершины, которые достижимы из <tex>q</tex> (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат <tex>M</tex> содержит циклы. Теперь перестроим автомат так, что он будет принимать слова, "зацикленные" вокруг <tex>q</tex>, то есть начинающиеся с <tex>q</tex> и после достижения терминальной вершины продолжающиеся с <tex>q_0</tex>(см. рис. 2). Для этого стартовой вершиной сделаем <tex>q</tex> и построим от нее часть <tex>A_2</tex>. Теперь добавим состояние <tex>q_0</tex> и соединим с ним все терминальные состояния из <tex>A_2</tex> с помощью <tex>\varepsilon-</tex>переходов. Далее построим от <tex>q_0</tex> часть <tex>A_1</tex>. Добавим вершину <tex>q'</tex>, эквивалентную <tex>q</tex>, и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины <tex>q</tex>. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой # Содержит ли <tex>q</tex>. Для этого создадим новую стартовую вершину <tex>q_0'</tex> и свяжем ее со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярнымпалиндром.