Замкнутость регулярных языков относительно различных операций

Теорема

Теорема:

Пусть [math]L_1, L_2[/math] — регулярные языки над одним алфавитом [math]\Sigma[/math]. Тогда следующие языки также являются регулярными: Языки, полученные путём применения следующих теоретико-множественных операций: [math]L_1 \cup L_2[/math], [math]\overline{L_1}[/math], [math]L_1 \cap L_2[/math], [math]L_1 \setminus L_2[/math]; [math]L_1^*[/math]; [math]L_1 L_2[/math]; [math]\overset{\leftarrow}{L_1}[/math].

Доказательство:

[math]\triangleright[/math]

Как известно, классы регулярных и автоматных языков совпадают. Пусть языки [math]L_1[/math] и [math]L_2[/math] распознаются автоматами [math]A_1 = \langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle [/math] и [math]A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \Sigma \rightarrow 2^{Q_2} \rangle [/math] соответственно. [math]L_1 \cup L_2[/math] является регулярным по определению регулярных языков. Рассмотрим автомат [math]A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle [/math], то есть автомат [math]A[/math], в котором терминальные и нетерминальные состояния инвертированы (при таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.) Очевидно, он допускает те и только те слова, которые не допускает автомат [math]A_1[/math], а значит, задаёт язык [math]\overline{L_1}[/math]. Таким образом, [math]\overline{L_1}[/math] — регулярный. [math]L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}[/math]. Тогда [math]L_1 \cap L_2[/math] — регулярный. Также автомат для пересечения языков можно построить явно, используя конструкцию произведения автоматов. [math]L_1 \setminus L_2 = L_1 \cap \overline{L_2}[/math]. Тогда [math]L_1 \setminus L_2[/math] — регулярный. [math]L_1^*[/math] является регулярным по определению регулярных языков. [math]L_1 L_2[/math] также является регулярным по определению регулярных языков. Рассмотрим НКА c [math]\varepsilon[/math]-переходами [math]A_1' = \langle \Sigma, Q_1, s' , \lbrace s_1 \rbrace, \delta_1' \rangle [/math], где [math]\delta_1' (v,c) = \lbrace u | \delta_1(u,c) = v \rbrace [/math]; [math]\delta_1'(s', \varepsilon) = \lbrace T_i \rbrace[/math]. Если в исходном автомате путь по [math]\alpha[/math] из [math]s_1[/math] приводил в терминальное состояние, то в новом автомате существует путь по [math]\alpha[/math] из этого терминального состояния в [math]s_1[/math] (и наоборот). Следовательно, этот автомат распознает в точности развернутые слова языка [math]L_1[/math]. Тогда язык [math]\overset{\leftarrow}{L_1}[/math] — регулярный.

[math]\triangleleft[/math]

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

Гомоморфизм цепочек

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

[math]L \subset \Sigma_1^*[/math] — регулярный , [math]\varphi:\Sigma_1^* \rightarrow \Sigma_2^* [/math] — гомоморфизм цепочек. Тогда [math]\varphi(L)[/math] — регулярный.

[math]\triangleright[/math]

Рассмотрим ДКА, распознающий [math]L[/math]. Заменим в нем все переходы по символам на переходы по их образам при гомоморфизме. Полученный автомат (с переходами по строкам) распознает в точности [math]\varphi(L)[/math] и имеет эквивалентный ДКА.

[math]\triangleleft[/math]

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

[math]L \subset \Sigma_2^*[/math] — регулярный , [math]\varphi:\Sigma_1^* \rightarrow \Sigma_2^* [/math] — гомоморфизм цепочек. Тогда [math]\varphi^{-1}(L)[/math] — регулярный.

[math]\triangleright[/math]

Рассмотрим ДКА, распознающий [math]L[/math]. Отследим для каждого состояния [math]u[/math] и символа [math]c[/math] строку [math]\varphi(c)[/math]: [math] \langle u,\varphi(c) \rangle \vdash^* \langle v,\varepsilon \rangle[/math] и положим [math]\delta (u,c) = v[/math] в новом автомате (на том же множестве состояний). Автомат с построенной таким образом функцией переходов, очевидно, распознает слова языка [math]\varphi^{-1}(L)[/math] и только их.

[math]\triangleleft[/math]

Язык half(L)

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

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

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

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

Пусть [math]L[/math] — регулярный язык. Тогда язык [math]\mathrm{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 \mathrm{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 \mathrm{half(L)}[/math]. Если мы сможем отслеживать [math]S_n[/math] и [math]q_i[/math], то сможем определять, верно ли, что [math]x \in \mathrm{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]\mathrm{half(L)}[/math].Таким образом, мы построили ДКА, который допускает язык [math]\mathrm{half(L)}[/math]. Следовательно, данный язык является регулярным.

[math]\triangleleft[/math]

Язык cycle(L)

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

Определим [math]\mathrm{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]\mathrm{cycle(L)} = \{ 01, 10, 011, 110, 101 \}[/math].

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

Пусть [math]L[/math] — регулярный язык. Тогда язык [math]\mathrm{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]\mathrm{cycle(L)}[/math], следовательно, данный язык является регулярным.

[math]\triangleleft[/math]

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

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

Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.

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

Язык alt(L, M)

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

Пусть [math]w = w_1 w_2 \dots w_n[/math] и [math]x = x_1 x_2 \dots x_n[/math]. Определим [math]alternation(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]\mathrm{alt(L, M)} = \{ alternation(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]\mathrm{alt(L, M)} = \{ 1101, 0101, 10010011 \}[/math].

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

Пусть [math]L[/math] и [math]M[/math] — регулярные языки. Тогда [math]\mathrm{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]\mathrm{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]\mathrm{alt(L, M)}[/math], что доказывает, что [math]\mathrm{alt(L, M)}[/math] является регулярным.

[math]\triangleleft[/math]

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

Рис. 6. Автомат, принимающий язык [math]\mathrm{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]. Мы видим, что построенные по функции [math]\delta'[/math] переходы на каждом шаге меняют состояние одного из автоматов, а именно того, по которому происходит переход, сохраняя состояние другого для следующего шага. Таким образом, каждый следующий символ получен из автомата, отличного от того, что был использован на предыдущем шаге. Декартово произведение состояний гарантирует, что мы рассмотрим все состояния и переходы изначальных автоматов. Для данного примера мы получаем, что [math]\mathrm{alt(L, M)} = \{ 1010 \}[/math].

См. также

• Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)
• Теорема Клини (совпадение классов автоматных и регулярных языков)

Источники

• Хопкрофт Д., Мотвани Р., Ульман Д. "Введение в теорию автоматов, языков и вычислений", 2-е изд. : Пер. с англ. — М.:Издательский дом «Вильямс», 2002. — С. 149 — ISBN 5-8459-0261-4