Изменения

==Основные операции={{Теорема|statement=Пусть <tex>L_1, L_2</tex> {{--- }} [[Регулярные языки: два определения и их эквивалентность|регулярные языки]] над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:#Языки, полученные путём применения теоретико-множественных операций:#*<tex>L_1 \cup L_2</tex>,#*<tex>\overline{L_1 L_2}</tex>,#*<tex>L_1^*\cap L_2</tex>,#*<tex>L_1 \overline{L_1}setminus L_2</tex>;#<tex>L_1 \cap L_2^*</tex>;#<tex>L_1 \setminus L_2</tex>;#<tex>\overset{\leftarrow}{L_1}</tex>.===Доказательство==|proof=Свойства 1,2Как известно,3 непосредственно следуют из определения [[Регулярные языки: два определения и их эквивалентность|регулярных языков]]. При доказательстве дальнейших свойств воспользуемся [[Теорема Клини (совпадение классов автоматных и регулярных языков|эквивалентностью классы регулярных и автоматных языковсовпадают]]. Пусть языки <tex>L_1</tex> и <tex>L_2</tex> распознаются автоматами <br /> <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> соответственно.##*<ol start="4"tex>L_1 \cup L_2<li><p/tex>является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].Инвертируем множество допускающих состояний: рассмотрим #*Рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle </tex>. Очевидно, он допускает те и только те слова, которые не допускает то есть автомат <tex>A_1A</tex>, в котором терминальные и нетерминальные состояния инвертированы.<br/>(При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.) Очевидно, он допускает те и только те слова, которые не допускает автомат </ptex>A_1</litex> <li><p>Следует из пунктов 1 и 4, т.к. а значит, задаёт язык <tex>L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}</tex>. <br/> Автомат для пересечения языков можно построить явноТаким образом, используя конструкцию ''произведения автоматов'': </p><p> <tex>A = \langle \Sigma , Q , s , T , \delta : Q \times \Sigma \rightarrow 2^overline{QL_1} \rangle </tex>{{---}} регулярный.#*Заметим, где <br/> что <tex>Q L_1 \cap L_2 = \lbrace overline{\langle q_1, q_2 overline{L_1} \rangle | q_1 cup \in Q_1, q_2 \in Q_2 \rbraceoverline{L_2}}</tex> <br/> . Тогда по уже доказанному <tex>s = L_1 \langle s_1, s_2 \ranglecap L_2</tex> <br/>{{---}} регулярный.#*<tex>T L_1 \cap L_2 = \lbrace overline{\langle t_1, t_2 overline{L_1} \rangle | t_1 cup \in T_1, t_2 \in T_2 \rbraceoverline{L_2}}</tex> <br/> . Тогда <tex>L_1 \delta (\langle q_1,q_2 \rangle, c) = \langle \delta_1 (q_1, c),\delta_2 (q_2, c) \ranglecap L_2</tex> </p></li><li><p>{{---}} регулярный.#*<tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}</tex>. Соответствующий автомат строится как произведение автоматов для языков Тогда <tex>L_1\setminus L_2</tex> и <tex>\overline {L_2{---}}регулярный.#</tex> L_1^*</ptex>является регулярным по определению [[Регулярные языки: два определения и их эквивалентность|регулярных языков]].#</litex>L_1 L_2<li><p/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) = T_1</tex>.<br/>Если в исходном автомате путь по <tex>\alpha</tex> из <tex>s_1</tex> приводил в терминальное состояние, то в новом автомате существует путь по <tex>\alpha</tex> из этого терминального состояния в <tex>s_1</tex> (и наоборот). Следовательно, этот автомат распознает в точности развернутые слова языка <tex>L_1</tex>, и из [[Автоматы_с_eps-переходами._Eps-замыкание|эквивалентности <tex>\varepsilon</tex>-НКА и ДКА]] Тогда язык <tex>\overset{\leftarrow}{L_1}</tex> {{- --}} регулярный.</p></li></ol>}}

|definition=Отображение <tex>\varphi : \Sigma_1^* \to \Sigma_2^*</tex>, сохраняющее операцию конкатенации <tex>(\varphi(\alpha\beta) = \varphi(\alpha) \varphi(\beta))</tex>, называется '''гомоморфизмом'''.

|definition='''Образом языка ''' <tex>L \subset \Sigma_1^*</tex> при гомоморфизме <tex>\varphi: \Sigma_1^* \rightarrow \Sigma_2^*</tex> называется язык <tex>\varphi (L) \overset{\underset{\mathrm{def}}{}}{=} \lbrace \varphi (x) | x \in L \rbrace</tex>.

|definition='''Прообразом языка ''' <tex>L \subset \Sigma_2^*</tex> при гомоморфизме <tex>\varphi: \Sigma_1^* \rightarrow \Sigma_2^*</tex> называется язык <tex>\varphi^{-1} (L) \overset{\underset{\mathrm{def}}{}}{=} \lbrace x | \varphi (x) \in L \rbrace</tex>.

<tex>L \subset \Sigma_1^*</tex> – {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> – {{---}} гомоморфизм. Тогда <tex>\varphi(L)</tex> – {{---}} регулярный.

<tex>L \subset \Sigma_2^*</tex> – {{---}} регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> – {{---}} гомоморфизм. Тогда <tex>\varphi^{-1}(L)</tex> – {{---}} регулярный.