Изменения

==Основные операцииТеорема =={{Теорема|statement=Пусть <tex>L_1, L_2</tex> {{-- -}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки ]] над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:#Языки, полученные путём применения следующих теоретико-множественных операций:#*<tex>L_1 \cup L_2</tex>,#*<tex>\overline{L_1 }</tex>,#*<tex>L_1 \cap L_2</tex>,#*<tex>L_1\setminus L_2</tex>;#<tex>L_1^*</tex>;#<tex>L_1 L_2</tex>;#<tex>\overset{\leftarrow}{L_1}</tex>.|proof=Как известно, [[Теорема Клини (совпадение классов автоматных и регулярных языков|классы регулярных и автоматных языков совпадают]]. Пусть языки <tex>L_1</tex> и <tex>L_2</tex> распознаются автоматами <tex>A_1 = \langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle </tex> и <tex>A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \Sigma \rightarrow 2^{Q_2} \rangle </tex> соответственно.##*<tex>L_1 \cup L_2</tex>является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].#*Рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle </tex>, то есть автомат <tex>A</tex>, в котором терминальные и нетерминальные состояния инвертированы (при таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.) Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>, а значит, задаёт язык <tex>\overline{L_1}</tex>. Таким образом, <tex>\overline{L_1}</tex>{{---}} регулярный.#*<tex>L_1 \cap L_2= \overline{\overline{L_1} \cup \overline{L_2}}</tex>. Тогда <tex>L_1 \cap L_2</tex> {{---}} регулярный. Также автомат для пересечения языков можно построить явно, используя конструкцию [[Прямое произведение ДКА|произведения автоматов]].#*<tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}</tex>. Тогда <tex>L_1 \setminus L_2</tex>{{---}} регулярный.#<tex>L_1^*</tex> является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].#<tex>L_1 L_2</tex> также является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].#Рассмотрим [[Автоматы_с_eps-переходами._Eps-замыкание|НКА c <tex>\varepsilon</tex>-переходами]] <tex>A_1' =\langle \Sigma, Q_1, s' , \lbrace s_1 \rbrace, \delta_1' \rangle </tex>, где <tex>\delta_1' (v,c) =\lbrace u | \delta_1(u,c) =Доказательствоv \rbrace </tex>; <tex>\delta_1'(s', \varepsilon) =\lbrace T_i \rbrace</tex>. Если в исходном автомате путь по <tex>\alpha</tex> из <tex>s_1</tex> приводил в терминальное состояние, то в новом автомате существует путь по <tex>\alpha</tex> из этого терминального состояния в <tex>s_1</tex> (и наоборот). Следовательно, этот автомат распознает в точности развернутые слова языка <tex>L_1</tex>. Тогда язык <tex>\overset{\leftarrow}{L_1}</tex> {{---}} регулярный.}}== Примеры доказательств ===== Гомоморфизм цепочек ==={{Утверждение|id=st1|statement=<tex>L \subset \Sigma_1^*</tex> {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> {{---}} [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм_языков | гомоморфизм цепочек]]. Тогда <tex>\varphi(L)</tex> {{---}} регулярный.|proof=Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]], распознающий <tex>L</tex>. Заменим в нем все переходы по символам на переходы по их образам при гомоморфизме. Полученный автомат (с переходами по строкам) распознает в точности <tex>\varphi(L)</tex> и [[Автоматы_с_eps-переходами._Eps-замыкание|имеет эквивалентный ДКА]].}}{{Утверждение|id=st2Свойства |statement=<tex>L \subset \Sigma_2^*</tex> {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> {{---}} [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками#Гомоморфизм_языков | гомоморфизм цепочек]]. Тогда <tex>\varphi^{-1}(L)</tex> {{---}} регулярный.|proof=Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]],2распознающий <tex>L</tex>. Отследим для каждого состояния <tex>u</tex> и символа <tex>c</tex> строку <tex>\varphi(c)</tex>: <tex> \langle u,\varphi(c) \rangle \vdash^* \langle v,\varepsilon \rangle</tex> и положим <tex>\delta (u,c) = v</tex> в новом автомате (на том же множестве состояний). Автомат с построенной таким образом функцией переходов, очевидно, распознает слова языка <tex>\varphi^{-1}(L)</tex> и только их.}}=== Язык half(L) ==={{Определение|definition = Определим <tex>\mathrm{half(L)}</tex> как множество первых половин цепочек языка <tex>L</tex>, то есть множество <tex>\{ w \mid \exists x : wx \in L \land |w| = |x| \}</tex>. }}Например, если <tex>L = \{ \varepsilon, 0010, 011, 010110 \}</tex>, то <tex>\mathrm{half(L)} = \{ \varepsilon, 00, 010 \}</tex>. Заметим,3 непосредственно следуют из определения регулярных языковчто цепочки нечетной длины не влияют на <tex>\mathrm{half(L)}</tex>.

При доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и автоматных языков. {{Утверждение|id = st3|statement =Пусть языки <tex>L_1L</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярный язык]]. Тогда язык <tex>L_2\mathrm{half(L)}</tex> распознаются автоматами также регулярен.|proof =Так как <tex>L<br /tex> {{---}} регулярный язык, то существует ДКА <tex>A_1 M = \langle \Sigma , Q_1 Q , s_1 q_0 , T_1 F , \delta_1 : Q_1 delta \times rangle </tex>, допускающий его. Рассмотрим строку <tex>x</tex>. Для того, чтобы проверить, что <tex>x \Sigma in \rightarrow 2^mathrm{Q_1half(L)} \rangle </tex> , нам надо убедиться, что существует строка <tex>y</tex> такой же длины, что и <tex>A_2 x</tex>, которая, будучи сконкатенированной с <tex>x</tex>, даст строку из <tex>L</tex>, то есть если на вход автомату подать <tex>xy</tex>, то в конце обработки мы окажемся в терминальном состоянии. Предположим, что автомат, закончив обработку <tex>x</tex>, находится в состоянии <tex>q_i</tex>, то есть <tex>\delta(q_0, x) = \langle \Sigma q_i</tex>. Мы должны проверить, Q_2 что существует строка <tex>y, s_2 |y| = |x|, T_2 </tex> которая ведет из состояния <tex>q_i</tex> до какого-нибудь терминального состояния <tex>M</tex>, то есть <tex>\delta_2 : Q_2 delta(q_i, y) \times \Sigma \rightarrow 2^{Q_2} \rangle in F</tex> соответственно.

Предположим, что мы прошли <tex>n</tex> вершин автомата, то есть <ol starttex>|x| ="4"n</tex>. Обозначим за <litex>S_n<p/tex>Инвертируем множество допускающих всех состояний: рассмотрим автомат , с которых можно попасть в терминальные за <tex>n</tex> шагов. Тогда <tex>A_1' = q_i \in S_n \Leftrightarrow x \langle in \Sigma mathrm{half(L)}</tex>. Если мы сможем отслеживать <tex>S_n</tex> и <tex>q_i</tex>, Q_1 то сможем определять, s_1 верно ли, Q_1 что <tex>x \in \setminus T_1 mathrm{half(L)}</tex>. Заметим, что <tex>S_0 \delta_1 \rangle equiv F</tex>. Очевидно, он допускает те мы можем построить <tex>S_{n+1}</tex> зная <tex>S_n</tex> и только те слова, которые не допускает автомат <tex>A_1\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' \}<br/tex>При таком построении следует помнить{{---}} множество состояний, что если из которых есть переход в исходном автомате было опущено дьявольское какое-либо состояние, его нужно явно добавить из <tex>S_n</tex> (по единственному символу). Теперь надо найти способ отслеживать и сделать допускающим.обновлять </ptex>S_n</litex>.

Построим ДКА <litex>M'</tex>, который будет хранить эту информацию в своих состояниях. Определим <tex>Q' = Q \times 2^Q</tex>, то есть каждое состояние <ptex>M'</tex>Следует {{---}} это пара из пунктов 1 одиночного состояния из <tex>M</tex> и 4множества состояний из <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>L_1 \cap L_2 delta'((q, S), a) = (\overlinedelta(q, a), prev(S))</tex>. Начальное состояние <tex>q_0' = (q_0, S_0) = (q_0, F)</tex>. Множество терминальных состояний {{---}} <tex>F' = \overline{L_1} (q, S) \mid q \in S, S \cup in 2^Q \overline{L_2}}</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': </ptex> допускает язык <tex>\mathrm{half(L)}<p/tex>.Таким образом, мы построили ДКА, который допускает язык <tex>\mathrm{half(L)}</tex>. Следовательно, данный язык является регулярным.}}=== Язык cycle(L) ==={{Определение|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>.

{{Утверждение|id = st5|statement =Пусть <tex>A 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 , s q_0 , T 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>\times 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>\Sigma varepsilon</tex>-переходами со всеми перестроенными автоматами (зацикленными вокруг всех подходящих <tex>q</tex>), в том числе и с изначальным автоматом. Построенный автомат допускает язык <tex>\rightarrow 2^mathrm{Qcycle(L)}</tex>, следовательно, данный язык является регулярным.}} \rangle [[Файл:Ex_1_before.jpg|left|thumb|260px|Рис. 3. Автомат, принимающий язык <tex>L</tex>.]][[Файл:Ex_1_after.jpg|right|thumb|380px|Рис. 4. Автомат, где принимающий язык <tex>\mathrm{cycle(L)}<br/tex>.]]Для лучшего понимания алгоритма перестроения автомата рассмотрим пример.

На рис. 3 представлен автомат, допускающий язык <tex>Q L = \lbrace { ab, abb, ac \langle q_1}</tex>. На рис. 4 показано, как этот автомат был перестроен. Были добавлены части, q_2 зацикленные относительно вершин <tex>2</tex> и <tex>3</tex>. Появилась новая стартовая вершина <tex>0</tex>, которая связана <tex>\varepsilon</tex>-переходами с изначальным автоматом и его измененными версиями. Данный автомат распознает язык <tex>\rangle | q_1 mathrm{cycle(L)} = \in Q_1{ ab, abb, ac, ba, bba, q_2 ca, bab \in Q_2 \rbrace}</tex>: первые три слова распознает первая часть, которая совпадает с изначальным автоматом; следующие три {{---}} вторая, перестроенная относительно вершины <tex>2</tex> ; последнее слово распознает третья часть, зацикленная относительно вершины <tex>3<br/tex>.

<texbr><br><br><br><br><br>s = \langle s_1, s_2 \rangle</texbr><br><br><br> <br/>

<tex>T = \lbrace \langle t_1, t_2 \rangle | t_1 \in T_1, t_2 \in T_2 \rbrace</tex> <br/> <tex>\delta (\langle q_1,q_2 \rangle, c) = \langle \delta_1 = Язык alt(q_1)L,\delta_2 (q_2M) \rangle</tex> </p></li><li><p><tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}</tex>. Соответствующий автомат строится как произведение автоматов для языков <tex>L_1</tex> и <tex>\overline {L_2}</tex> </p></li></ol> ==Прямой и обратный гомоморфизмы=={{Определение|definition=Отображение <tex>\varphi : \Sigma_1^* \to \Sigma_2^*</tex>, сохраняющее операцию конкатенации <tex>(\varphi(\alpha\beta) = \varphi(\alpha) \varphi(\beta))</tex>, называется гомоморфизмом.}}Гомоморфизм однозначно задается значениями на алфавите: <tex>\varphi(\overline{c_1 c_2 \ldots c_k}) = \varphi(c_1) \varphi(c_2)\ldots \varphi(c_k)</tex>.

|definition=Образом языка Пусть <tex>L \subset w = w_1 w_2 \Sigma_1^*dots w_n</tex> при гомоморфизме и <tex>x = x_1 x_2 \varphi: \Sigma_1^* \rightarrow \Sigma_2^*dots x_n</tex> называется язык . Определим <tex>\varphi alternation(Lw, x) \overset{\underset{\mathrm{def}}{}}{=} \lbrace \varphi (x) | x w_1 x_1 w_2 x_2 \in L \rbracedots w_n x_n</tex>.}}Теперь распространим это определение:

|definition=Прообразом языка Пусть <tex>L \subset \Sigma_2^*</tex> при гомоморфизме и <tex>M</tex> {{---}} два языка над одним алфавитом <tex>\varphi: \Sigma_1^* \rightarrow \Sigma_2^*Sigma</tex> называется язык . Тогда <tex>\varphi^mathrm{-1} alt(L, M) } = \overset{alternation(w, x) \underset{mid |w| = |x|, w \in L, x \in M \mathrm{def}</tex>.}}Например, если <tex>L = \{10, 00, 111, 1001 \}}</tex> и <tex>M = \{=11, 0101 \} </tex>, то <tex>\lbrace x | \varphi mathrm{alt(xL, M) } = \in L { 1101, 0101, 10010011 \rbrace}</tex>.}}

|id=st1st4|statement=Пусть <tex>L</tex> и <tex>M</tex> {{---}} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]]. Тогда <tex>\mathrm{alt(L, M)}</tex> также является регулярным.|proof = Так как <tex>L </tex> и <tex>M</tex> {{---}} регулярные языки, то существуют ДКА <tex>D_L = \subset langle \Sigma_1^*Sigma , Q_L , q_{0L} , F_L, \delta_L \rangle</tex> – регулярный , распознающий язык <tex>L</tex>, и <tex>D_M = \varphi:langle \Sigma_1^* Sigma , Q_M , q_{0M} , F_M, \rightarrow delta_M \Sigma_2^* rangle</tex>, распознающий язык <tex>M</tex> – гомоморфизм. Тогда Построим автомат <tex>D_{alt}</tex>, который будет распознавать язык <tex>\varphimathrm{alt(L, M)}</tex> – регулярный.|proof=Рассмотрим [[Детерминированные_конечные_автоматы|ДКА]]Идея следующая: каждое состояние этого автомата будем описывать тремя значениями <tex>(p, q, b)</tex>, где <tex>p \in Q_L</tex>, распознающий <tex>Lq \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>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>\varphidelta'((Lp, 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> и [[Автоматы_с_eps<tex>D_M</tex> {{--переходами._Eps-замыкание|}} все четные, а так же <tex>w</tex> имеет эквивалентный ДКА]]четную длину. Следовательно, <tex>D_{alt}</tex> распознает язык <tex>\mathrm{alt(L, M)}</tex>, что доказывает, что <tex>\mathrm{alt(L, M)}</tex> является регулярным.

{{Утверждение|id=st1|statement=<texbr><br>L \subset \Sigma_2^*</texbr> – регулярный , <texbr>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </texbr> – гомоморфизм. Тогда <texbr>\varphi^{-1}(L)</texbr> – регулярный == См.также ==|proof=* [[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]Рассмотрим * [[Детерминированные_конечные_автоматы|ДКАТеорема Клини (совпадение классов автоматных и регулярных языков)]] == Источники ==* Хопкрофт Д., распознающий <tex>L</tex>Мотвани Р. Отследим для каждого состояния <tex>u</tex> и символа <tex>c</tex> строку <tex>\varphi(c)</tex>: <tex> \langle u,\varphi(c) \rangle \vdash^* \langle vУльман Д. "Введение в теорию автоматов,\varepsilon \rangle</tex> языков и положим <tex>\delta (uвычислений",c) = v</tex> в новом автомате (на том же множестве состояний)2-е изд. : Пер. Автомат с построенной таким образом функцией переходовангл. — М.:Издательский дом «Вильямс», очевидно, распознает слова языка <tex>\varphi^2002. {{-1--}(L)</tex> } С. 149 — ISBN 5-8459-0261-4[[Категория: Теория формальных языков]][[Категория: Автоматы и только их.регулярные языки]]}}[[Категория: Свойства конечных автоматов]]