|
|
| (не показано 8 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| − | == Примеры доказательств == | + | {{Теорема |
| − | === Язык <tex>half(L)</tex> ===
| + | |statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| − | {{Определение | + | |proof= |
| − | |definition = Определим <tex>half(L)</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid </tex> существует <tex>x</tex>, для которой <tex>wx \in L</tex>, причем <tex>|w| = |x| \}</tex>. }}
| + | Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы. |
| − | Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>half(L) = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>half(L)</tex>.
| |
| | | | |
| − | {{Утверждение
| + | Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики: |
| − | |id = st3
| + | * <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>. |
| − | |statement =
| + | * <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</tex> {{---}} регулярный язык. Тогда язык <tex>half(L)</tex> также регулярен.
| + | |
| − | |proof =
| + | Если данный экземпляр ПСП имеет решение, то <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>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in half(L)</tex>, нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</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) \in F</tex>.<br>
| |
| − | Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in half(L)</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in half(L)</tex>. Заметим, что <tex>S_0 \equiv F</tex>. Очевидно мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и <tex>\delta</tex>: <tex>S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \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 2^Q</tex>, то есть каждое состояние <tex>M'</tex> {{---}} это пара из одиночного состояния из <tex>M</tex> и множества состояний из <tex>M</tex>. Функцию перехода <tex>\delta'</tex> автомата <tex>M'</tex> определим так, чтобы если по какой-то строке <tex>x</tex> длины <tex>n</tex> в автомате <tex>M</tex> мы перешли в состояние <tex>q_i</tex>, то по этой же строке в автомате <tex>M'</tex> мы перейдем в состояние <tex>(q_i, S_n)</tex>, где <tex>S_n</tex> {{---}} множество состояний из <tex>M</tex>, определенное выше. Вспомним приведенную выше функцию <tex>prev(S_n) = S_{n+1}</tex>. С ее помощью мы можем определить функцию перехода следующим образом: <tex>\delta'((q, S), a) = (\delta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \{ (q, S) \mid q \in S, S \in 2^Q \}</tex>.<br>
| |
| − | Теперь по индукции не сложно доказать, что <tex>\delta'(q_0', x) = (\delta(q_0, x), S_n)</tex>, где <tex>|x| = n</tex>. По определению множества терминальных вершин, автомат <tex>M'</tex> допускает строку <tex>x</tex> тогда и только тогда, когда <tex>\delta(q_0, x) \in S_n</tex>. Следовательно, автомат <tex>M'</tex> допускает язык <tex>half(L)</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>half(L)</tex>. Следовательно, данный язык является регулярным.
| |
| − | }}
| |
| − | === Язык <tex>cycle(L)</tex> ===
| |
| − | {{Определение
| |
| − | |definition = Определим <tex>cycle(L)</tex> как множество <tex>\{ w \mid </tex> цепочку <tex>w</tex> можно представить в виде <tex>w = xy</tex>, где <tex>yx \in L \}</tex>. }}
| |
| − | Например, если <tex>L = \{ 01, 011 \}</tex>, то <tex>cycle(L) = \{ 01, 10, 011, 110, 101 \}</tex>.
| |
| | | | |
| − | {{Утверждение
| + | Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</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> {{---}} суффиксом. Разделим автомат на две части <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>.
| |
| | | | |
| − | <br><br><br><br><br><br><br><br><br><br><br> | + | По двум КС-грамматикам <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>alt(L, M)</tex> ===
| + | Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</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>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы: |
| − | |statement = Пусть <tex>L</tex> и <tex>M</tex> {{---}} регулярные языки. Тогда <tex>alt(L, M)</tex> также является регулярным. | + | # Содержит ли <tex>L</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}</tex>, который будет распознавать язык <tex>alt(L, M)</tex>. Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</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 = 1</tex>, то, соответственно, все наоборот. То есть у нас будут две функции перехода, выбирать нужную будем в зависимости от четности третьего параметра. Важно, что на каждом шаге мы инвертируем значение <tex>b</tex>, что гарантирует чередование. Определим автомат <tex>D_{alt} = \langle \Sigma, Q', q_0', F', \delta' \rangle</tex> следующим образом:
| + | # Содержит ли <tex>L</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 \}</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> является регулярным.
| |
| | }} | | }} |
| − | [[Файл:Alt ex 1.jpg|left|thumb|265px|Рис. 5. Автоматы для языков <tex>L</tex> и <tex>M</tex>.]]
| |
| − | [[Файл:Alt ex 2.jpg|right|thumb|390px|Рис. 6. Автомат, принимающий язык <tex>alt(L, M)</tex>.]]
| |
| − | Чтобы более наглядно показать, как строится автомат <tex>D_{alt}</tex>, разберем пример. Пусть <tex>L = \{ 1, 11 \}</tex> и <tex>M = \{ 00 \}</tex> (см. рис. 5). Все состояния нового автомата представлены на рис. 6. Стартовая вершина <tex>q_0' = (1, 1, 0)</tex>, множество терминальных вершин {{---}} <tex>F' = \{ (2, 3, 0), (3, 3, 0) \}</tex>.
| |
