|
|
| (не показано 6 промежуточных версий этого же участника) |
| Строка 1: |
Строка 1: |
| − | == Примеры доказательств ==
| + | {{Теорема |
| − | === Язык <tex>\mathrm{half(L)}</tex> === | + | |statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| − | {{Определение
| + | |proof= |
| − | |definition = Определим <tex>\mathrm{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>\mathrm{half(L)} = \{ \varepsilon, 00, 010 \}</tex>. Заметим, что цепочки нечетной длины не влияют на <tex>\mathrm{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>\mathrm{half(L)}</tex> также регулярен.
| |
| − | |proof =
| |
| − | Так как <tex>L</tex> {{---}} регулярный язык, то существует ДКА <tex>M = \langle \Sigma , Q , q_0 , F , \delta \rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \in \mathrm{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>.
| |
| − | | |
| − | Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <tex>|x| = n</tex>. Обозначим за <tex>S_n</tex> множество всех состояний, с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>q_i \in S_n \Leftrightarrow x \in \mathrm{half(L)}</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, то сможем определять, верно ли, что <tex>x \in \mathrm{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>.
| |
| − | | |
| − | Построим ДКА <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>.
| |
| | | | |
| − | Теперь по индукции не сложно доказать, что <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>\mathrm{half(L)}</tex>.Таким образом, мы построили ДКА, который допускает язык <tex>\mathrm{half(L)}</tex>. Следовательно, данный язык является регулярным.
| + | Если данный экземпляр ПСП имеет решение, то <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>\mathrm{cycle(L)}</tex> ===
| |
| − | {{Определение
| |
| − | |definition = Определим <tex>\mathrm{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>\mathrm{cycle(L)} = \{ 01, 10, 011, 110, 101 \}</tex>.
| |
| | | | |
| − | {{Утверждение
| + | Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| − | |id = st5
| |
| − | |statement =
| |
| − | Пусть <tex>L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>\mathrm{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> [[Автоматы_с_eps-переходами._Eps-замыкание|недетерминированный автомат с <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>\mathrm{cycle(L)}</tex>, следовательно, данный язык является регулярным.
| |
| | }} | | }} |
| − | [[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]]
| + | Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров. |
| − | [[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, принимающий язык <tex>\mathrm{cycle(L)}</tex>.]]
| |
| − | Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.
| |
| − | | |
| − | На рис. 3 представлен автомат, допускающий язык <tex>L = \{ ab, abb, ac \}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon-</tex>переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>\mathrm{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>\mathrm{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>\mathrm{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>\mathrm{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>\mathrm{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>\mathrm{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>\mathrm{alt(L, M)}</tex>, что доказывает, что <tex>\mathrm{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>\mathrm{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>. Мы видим, что построенные по функции <tex>\delta'</tex> переходы на каждом шаге меняют состояние одного из автоматов, а именно того, по которому происходит переход, сохраняя состояние другого для следующего шага. Таким образом, каждый следующий символ получен из автомата, отличного от того, что был использован на предыдущем шаге. Декартово произведение состояний гарантирует, что мы рассмотрим все состояния и переходы изначальных автоматов. Для данного примера мы получаем, что <tex>\mathrm{alt(L, M)} = \{ 1010 \}</tex>.
| |
