Изменения

{{Теорема|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> {{---}} регулярный язык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>. Следовательно, данный язык является регулярнымследовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима.

=== Язык <tex>alt(L, M)</tex> ==={{Определение|definition = Пусть <tex>w = w_1 w_2 \dots w_n</tex> и <tex>x = x_1 x_2 \dots x_n</tex>Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Определим <tex>alt(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n</tex>. Распространим это определение на языки следующим образом: пусть <tex>L</tex> и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\Sigma</tex>. Тогда <tex>alt(L, M) = \{ alt(w, x) \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, M) = \{ 1101, 0101, 10010011 \}</tex>Рассмотрим несколько примеров.

{{Утверждение|id = st4|statement = Пусть По двум КС-грамматикам <tex>LG_1</tex> и <tex>MG_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>altL(G_1)L, M(G_2)</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 = (G_1)\langle \Sigma , Q_M , q_{0M} , F_M, \delta_M \rangle</tex>, распознающий язык <tex>M</tex>. Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>alt(#L, M)</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, bG_2)\#</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>q</tex> останется неизменнойновый символ, <tex>b</tex> станет <tex>1</tex>, если <tex>b = 1</tex>, то, соответственно, все наоборот. То есть не встречающийся в зависимости от четности третьего параметра будем использовать две функции переходаалфавите. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>Заметим, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigmaпересечение языков непусто, Q', q_0', F', \delta' \rangleто есть </tex> следующим образом:# <tex>Q' = Q_L L(G_1) \times Q_M \times \{ 0, 1 \}</tex># <tex>q_0' = cap L(q_{0L}, q_{0M}, 0G_2)</tex># <tex>F' = F_L \times F_M ne \times \{ 0 \}varnothing </tex># <tex>\delta'((p, qтогда и только тогда, 0), a) = (\delta_L(p, a), q, 1)когда </tex> и <tex>\delta'L((p, q, 1), aG_1) = (p, \delta_M#L(q, a), 0G_2)\#</tex>Стартовая вершина имеет третий параметр <tex>b = 0</tex>, так как первое значение должно быть получено из автомата <tex>D_L</tex>содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1. Аналогично все терминальные вершины должны иметь то же значение последнего параметра, так как количество переходов должно быть четным и последний переход должен был быть осуществлен по автомату <tex>D_M</tex>8F|тандемный повтор]].}}

=== Язык Аналогично можно заметить, что пересечение <tex>cycleL(G_1) \cap L)</tex> ==={{Определение|definition = Определим <tex>cycle(LG_2)</tex> как множество <tex>\{ w ne \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xyvarnothing </tex>тогда и только тогда, где когда <tex>yx \in L (G_1)\}</tex>. }}Например, если <tex>#L = \{ 01, 011 \}</tex>, то <tex>cycle(LG_2) = \{ 01, 10, 011, 110, 101 \}^R</tex>содержит палиндром.

|id = st5|statement =Пусть дана грамматика <tex>LG</tex> {{---}} регулярный язык. Тогда язык , <tex>cycleL(G) = 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> {{---}} суффиксом. Разделим автомат на две части <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>, следовательно, данный язык является регулярнымпалиндром.