Изменения

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

{{Утверждение|id = st3|statement =Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык Для любого экземпляра ПСП <tex>half(L)</tex> также регулярен.|proof =Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma x_1, Q x_2, 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, \in S, S dots i_m \in 2^Q \}</tex>.<br>Теперь по индукции не сложно доказать{ 1, что <tex>\delta'(q_0'2, x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = dots n</tex>. По определению множества терминальных вершин\}, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>m \delta(q_0, x) geqslant 1 \in S_n}</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.}}=== Язык Если данный экземпляр ПСП имеет решение, то <tex>cycle(L)</tex> ==={{Определение|definition = Определим <tex>cycle(LG_2)</tex> как множество содержит хотя бы одну строку вида <tex>\{ w \mid </tex> цепочку <tex>#w</tex> можно представить в виде <tex>w = xy^R</tex>, где поэтому <tex>yx L(G_1) \in cap L (G_2) \ne \}varnothing</tex>. }}Например, и наоборот, если он не имеет решения, то <tex>L = \{ 01, 011 \}(G_2)</tex>не содержит строк такого вида, то соответственно <tex>cycleL(G_1) \cap L(G_2) = \{ 01, 10, 011, 110, 101 \}varnothing</tex>.

{{Утверждение|id = st5|statement =Пусть <tex>L</tex> {{---}} регулярный язык. Тогда язык <tex>cycle(L)</tex> также регулярен.|proof =[[Файл:Enfa_before.jpg|right|thumb|380px|Рис. 1. Разбиение автомата.]][[Файл:Enfa-after.jpg|right|thumb|380px|Рис. 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> overline{{---A}} суффиксом. Разделим автомат на две части <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>\varepsilon-</tex>переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>cycle(L)</tex>, следовательно, данный язык является регулярнымграмматик неразрешима.

[[Файл:Ex_1_beforeИз неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]][[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>cycle(L)</tex>.]]Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.<br>На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex>; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3</tex>Рассмотрим несколько примеров.

По двум КС-грамматикам <brtex>G_1<br/tex>и <brtex>G_2<br/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|конкатенации]] задаваемых ими языков <brtex>L(G_1)L(G_2)<br/tex>. По аналогии с этим мы можем рассматривать язык <brtex>L(G_1)\#L(G_2)\#<br/tex>, где <brtex>\#<br/tex>{{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <brtex>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>altL(L, MG_1)</tex> ==={{Определение|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>. Определим <tex>altcap L(w, xG_2) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>. Распространим это определение на языки следующим образом: пусть <tex>Lne \varnothing </tex> тогда и только тогда, когда <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>alt(L, M) = \{ alt(w, xG_1) \mid |w| = |x|, w \in L, x \in M \}</tex>.}}Например, если <tex>#L = \{ 10, 00, 111, 1001 \}</tex> и <tex>M = \{ 11, 0101 \}</tex>, то <tex>alt(L, MG_2) = \{ 1101, 0101, 10010011 \}^R</tex>содержит палиндром.

|id = st4|statement = Пусть дана грамматика <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки. Тогда <tex>alt(L, M)</tex> также является регулярным.|proof = Так как <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \langle \Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex>, распознающий язык <tex>L</tex>, и <tex>D_M = \langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}G</tex>, который будет распознавать язык <tex>alt(L, M)</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, bG)</tex>, где <tex>p \in Q_L</tex>, <tex>q \in Q_M</tex> и <tex>b \in \{ 1, 0 \}</tex>. Нам нужно организовать чередование переходов по состояниям автоматов, то есть если мы на определенном шаге перешли от одного состояния автомата <tex>D_L</tex> до другого, то на следующем мы обязаны совершить переход по состояниям автомата <tex>D_M</tex>. Для этого нам нужно обновлять состояние одного автомата и при этом сохранять состояние другого для следующего перехода. Тут мы будем использовать третье значение: если <tex>b = 0</tex>, то будет двигаться по состояниям первого автомата, то есть значение <tex>p</tex> при переходе в новое состояние автомата <tex>D_{alt}</tex> поменяется, <tex>q</tex> останется неизменной, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1L</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образомТогда следующие задачи неразрешимы:# Содержит ли <tex>Q' = Q_L \times Q_M \times \{ 0, 1 \}</tex># <tex>q_0' = (q_{0L}, q_{0M}, 0)</tex># <tex>F' = F_L \times F_M \times \{ 0 \}L</tex>тандемный повтор.# Содержит ли <tex>\delta'((p, q, 0), a) = (\delta_L(p, a), q, 1)</tex> и <tex>\delta'((p, q, 1), a) = (p, \delta_M(q, a), 0)</tex>Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>. Функция перехода <tex>\delta'</tex> использует <tex>\delta_L</tex> для получения нечетных символов и <tex>\delta_M</tex> для четных. Таким образом, <tex>D_{alt}</tex> состоит из чередующихся символов <tex>D_L</tex> и <tex>D_M</tex>. При этом <tex>D_{alt}</tex> принимает <tex>w</tex> тогда и только тогда, когда <tex>D_L</tex> последовательно принимает все нечетные символы <tex>w</tex> и <tex>D_M</tex> {{---}} все четные, а так же <tex>w</tex> имеет четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>alt(L, M)</tex>, что доказывает, что <tex>alt(L, M)</tex> является регулярнымпалиндром.