Обсуждение участницы:Анна

Примеры доказательств

Язык [math]half(L)[/math]

Определение:

Определим [math]half(L)[/math] как множество первых половин цепочек языка [math]L[/math], то есть множество [math]\{ w \mid [/math] существует [math]x[/math], для которой [math]wx \in L[/math], причем [math]|w| = |x| \}[/math].

Например, если [math]L = \{ \varepsilon, 0010, 011, 010110 \}[/math], то [math]half(L) = \{ \varepsilon, 00, 010 \}[/math]. Заметим, что цепочки нечетной длины не влияют на [math]half(L)[/math].

Утверждение:

Пусть [math]L[/math] — регулярный язык. Тогда язык [math]half(L)[/math] также регулярен.

[math]\triangleright[/math]

Так как [math]L[/math] — регулярный язык, то существует ДКА [math]M = \langle \Sigma , Q , q_0 , F , \delta \rangle [/math], допускающий его. Рассмотрим строку [math]x[/math]. Для того, чтобы проверить, что [math]x \in half(L)[/math], нам надо убедиться, что существует строка [math]y[/math] такой же длины, что и [math]x[/math], которая, будучи сконкатенированной с [math]x[/math], даст строку из [math]L[/math], то есть если на вход автомату подать [math]xy[/math], то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку [math]x[/math], находится в состоянии [math]q_i[/math], то есть [math]\delta(q_0, x) = q_i[/math]. Мы должны проверить, что существует строка [math]y, |y| = |x|,[/math] которая ведет из состояния [math]q_i[/math] до какого-нибудь терминального состояния [math]M[/math], то есть [math]\delta(q_i, y) \in F[/math]. Предположим, что мы прошли [math]n[/math] вершин автомата, то есть [math]|x| = n[/math]. Обозначим за [math]S_n[/math] множество всех состояний, с которых можно попасть в терминальные за [math]n[/math] шагов. Тогда [math]q_i \in S_n \Leftrightarrow x \in half(L)[/math]. Если мы сможем отслеживать [math]S_n[/math] и [math]q_i[/math], то сможем определять, верно ли, что [math]x \in half(L)[/math]. Заметим, что [math]S_0 \equiv F[/math]. Очевидно мы можем построить [math]S_{n+1}[/math] зная [math]S_n[/math] и [math]\delta[/math]: [math]S_{n+1} = prev(S_n) = \{ q \in Q \mid \exists a \in \Sigma, q' \in S_n, \delta(q, a) = q' \}[/math] — множество состояний, из которых есть переход в какое-либо состояние из [math]S_n[/math] (по единственному символу). Теперь надо найти способ отслеживать и обновлять [math]S_n[/math]. Построим ДКА [math]M'[/math], который будет хранить эту информацию в своих состояниях. Определим [math]Q' = Q \times 2^Q[/math], то есть каждое состояние [math]M'[/math] — это пара из одиночного состояния из [math]M[/math] и множества состояний из [math]M[/math]. Функцию перехода [math]\delta'[/math] автомата [math]M'[/math] определим так, чтобы если по какой-то строке [math]x[/math] длины [math]n[/math] в автомате [math]M[/math] мы перешли в состояние [math]q_i[/math], то по этой же строке в автомате [math]M'[/math] мы перейдем в состояние [math](q_i, S_n)[/math], где [math]S_n[/math] — множество состояний из [math]M[/math], определенное выше. Вспомним приведенную выше функцию [math]prev(S_n) = S_{n+1}[/math]. С ее помощью мы можем определить функцию перехода следующим образом: [math]\delta'((q, S), a) = (\delta(q, a), prev(S))[/math]. Начальное состояние [math]q_0' = (q_0, S_0) = (q_0, F)[/math]. Множество терминальных состояний — [math]F' = \{ (q, S) \mid q \in S, S \in 2^Q \}[/math]. Теперь по индукции не сложно доказать, что [math]\delta'(q_0', x) = (\delta(q_0, x), S_n)[/math], где [math]|x| = n[/math]. По определению множества терминальных вершин, автомат [math]M'[/math] допускает строку [math]x[/math] тогда и только тогда, когда [math]\delta(q_0, x) \in S_n[/math]. Следовательно, автомат [math]M'[/math] допускает язык [math]half(L)[/math].Таким образом, мы построили ДКА, который допускает язык [math]half(L)[/math]. Следовательно, данный язык является регулярным.

[math]\triangleleft[/math]

Язык [math]cycle(L)[/math]

Определение:

Определим [math]cycle(L)[/math] как множество [math]\{ w \mid [/math] цепочку [math]w[/math] можно представить в виде [math]w = xy[/math], где [math]yx \in L \}[/math].

Например, если [math]L = \{ 01, 011 \}[/math], то [math]cycle(L) = \{ 01, 10, 011, 110, 101 \}[/math].

Утверждение:

Пусть [math]L[/math] — регулярный язык. Тогда язык [math]cycle(L)[/math] также регулярен.

[math]\triangleright[/math]

Рис. 1. Разбиение автомата. Рис. 2. Перестроение. Так как [math]L[/math] — регулярный язык, то существует допускающий его ДКА [math]M = \langle \Sigma , Q , q_0 , F , \delta \rangle [/math]. Построим из [math]M[/math] недетерминированный автомат с [math]\varepsilon-[/math]переходами следующим образом: рассмотрим состояние [math]q \in Q[/math], из которого есть переходы в другие состояния (то есть начиная с [math]q[/math] можно построить непустое слово, заканчивающееся в терминальной вершине). Тогда если какое-то слово проходит через это состояние, оно может быть зациклено таким образом, что его суффикс, начинающийся с [math]q[/math], станет префиксом нового слова, а префикс, заканчивающийся в [math]q[/math] — суффиксом. Разделим автомат на две части [math]A_1[/math] и [math]A_2[/math] такие, что [math]A_1[/math] будет содержать все вершины, из которых достижима [math]q[/math], а [math]A_2[/math] — все вершины, которые достижимы из [math]q[/math] (см. рис. 1). Заметим, что каждая вершина может содержаться в обеих частях одновременно, такое может случиться, если автомат [math]M[/math] содержит циклы. Теперь перестроим автомат так, что он будет принимать слова "зацикленные" вокруг [math]q[/math], то есть начинающиеся с [math]q[/math] и после достижения терминальной вершины продолжающиеся с [math]q_0[/math] (см. рис. 2). Для этого стартовой вершиной сделаем [math]q[/math] и построим от нее часть [math]A_2[/math]. Теперь добавим состояние [math]q_0[/math] и соединим с ним все терминальные состояния из [math]A_2[/math] с помощью [math]\varepsilon-[/math]переходов. Далее построим от [math]q_0[/math] часть [math]A_1[/math]. Добавим вершину [math]q'[/math], эквивалентную [math]q[/math], и сделаем ее терминальной. Данный автомат принимает слова, зацикленные вокруг выбранной вершины [math]q[/math]. Мы хотим, чтобы автомат принимал слова, зацикленные вокруг любой такой [math]q[/math]. Для этого создадим новую стартовую вершину [math]q_0'[/math] и свяжем ее [math]\varepsilon-[/math]переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих [math]q[/math]), в том числе и с изначальным автоматом. Построенный автомат допускает язык [math]cycle(L)[/math], следовательно, данный язык является регулярным.

[math]\triangleleft[/math]

Рис. 3. Автомат, принимающий язык [math]L[/math].

Рис. 4. Автомат, принимающий язык [math]cycle(L)[/math].

Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.
На рис. 3 представлен автомат, допускающий язык [math]L = \{ ab, abb, ac \}[/math]. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, зацикленные относительно вершин [math]2[/math] и [math]3[/math]. Появилась новая стартовая вершина [math]0[/math], которая связана [math]\varepsilon-[/math]переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык [math]cycle(L) = \{ ab, abb, ac, ba, bba, ca, bab \}[/math]: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три — вторая, перестроенная относительно вершины [math]2[/math]; последнее слово распознает третья часть, зацикленная относительно вершины [math]3[/math].

Язык [math]alt(L, M)[/math]

Определение:

Пусть [math]w = w_1 w_2 \dots w_n[/math] и [math]x = x_1 x_2 \dots x_n[/math]. Определим [math]alt(w, x) = w_1 x_1 w_2 x_2 \dots w_n x_n[/math]. Распространим это определение на языки следующим образом: пусть [math]L[/math] и [math]M[/math] — два языка над одним алфавитом [math]\Sigma[/math]. Тогда [math]alt(L, M) = \{ alt(w, x) \mid |w| = |x|, w \in L, x \in M \}[/math].

Например, если [math]L = \{ 10, 00, 111, 1001 \}[/math] и [math]M = \{ 11, 0101 \}[/math], то [math]alt(L, M) = \{ 1101, 0101, 10010011 \}[/math].

Утверждение:

Пусть [math]L[/math] и [math]M[/math] — регулярные языки. Тогда [math]alt(L, M)[/math] также является регулярным.

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Рис. 5. Автоматы для языков [math]L[/math] и [math]M[/math].

Рис. 6. Автомат, принимающий язык [math]alt(L, M)[/math].

Чтобы более наглядно показать, как строится автомат [math]D_{alt}[/math], разберем пример. Пусть [math]L = \{ 1, 11 \}[/math] и [math]M = \{ 00 \}[/math] (см. рис. 5). Все состояния нового автомата представлены на рис. 6. Стартовая вершина [math]q_0' = (1, 1, 0)[/math], множество терминальных вершин — [math]F' = \{ (2, 3, 0), (3, 3, 0) \}[/math].