==Основные операции==
Пусть <tex>L_1, L_2</tex> - регулярные языки над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:
#<tex>L_1 \cup L_2</tex>
#<tex>L_1 L_2</tex>
#<tex>L_1^*</tex>
#<tex>\overline{L_1}</tex>
#<tex>L_1 \cap L_2</tex>
#<tex>L_1 \setminus L_2</tex>
#<tex>\overset{\leftarrow}{L_1}</tex>
===Доказательство===
Свойства 1,2,3 непосредственно следуют из определения регулярных языков.

При доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и автоматных языков. Пусть языки <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> соответственно.

<ol start="4">
<li>
Инвертируем множество допускающих состояний: рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle </tex>. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>.
 
При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.
</li>

<li>
Следует из пунктов 1 и 4, т.к. <tex>L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}</tex>. 

Автомат для пересечения языков можно построить явно, используя конструкцию ''произведения автоматов'': 

<tex>A = \langle \Sigma , Q , s , T , \delta : Q \times \Sigma \rightarrow 2^{Q} \rangle </tex>, где 

<tex>Q = \lbrace \langle q_1, q_2 \rangle | q_1 \in Q_1, q_2 \in Q_2 \rbrace</tex> 

<tex>s = \langle s_1, s_2 \rangle</tex> 

<tex>T = \lbrace \langle t_1, t_2 \rangle | t_1 \in T_1, t_2 \in T_2 \rbrace</tex> 

<tex>\delta (\langle q_1,q_2 \rangle, c) = \langle \delta_1 (q_1),\delta_2 (q_2) \rangle</tex> 
</li>
<li>
<tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}</tex>.

Соответствующий автомат строится как произведение автоматов для языков <tex>L_1</tex> и <tex>\overline {L_2}</tex> 
</li>
<li>
Развернем все переходы назад и поменяем стартовое состояние с терминальными: рассмотрим [[Автоматы_с_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>. 
Если в исходном автомате путь по <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> - регулярный.

</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 \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>.
}}

{{Утверждение
|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=st1
|statement=
<tex>L \subset \Sigma_2^*</tex> – регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> – гомоморфизм. Тогда <tex>\varphi^{-1}(L)</tex> – регулярный.
|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> в новом автомате (на том же множестве состояний). Автомат с построенной таким образом функцией переходов, очевидно, распознает слова языка <tex>\varphi^{-1}(L)</tex> и только их.
}}

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

2010-10-08T04:03:09Z

MikhailOK: /* Прямой и обратный гомоморфизмы */

==Основные операции==
Пусть <tex>L_1, L_2</tex> - регулярные языки над одним алфавитом <tex>\Sigma</tex>. Тогда следующие языки также являются регулярными:
#<tex>L_1 \cup L_2</tex>
#<tex>L_1 L_2</tex>
#<tex>L_1^*</tex>
#<tex>\overline{L_1}</tex>
#<tex>L_1 \cap L_2</tex>
#<tex>L_1 \setminus L_2</tex>
===Доказательство===
Свойства 1,2,3 непосредственно следуют из определения регулярных языков.

При доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и автоматных языков. Пусть языки <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> соответственно.

<ol start="4">
<li>
Инвертируем множество допускающих состояний: рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 \rangle </tex>. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>.
 
При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.
</li>

<li>
Следует из пунктов 1 и 4, т.к. <tex>L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}</tex>. 

Автомат для пересечения языков можно построить явно, используя конструкцию ''произведения автоматов'': 

<tex>A = \langle \Sigma , Q , s , T , \delta : Q \times \Sigma \rightarrow 2^{Q} \rangle </tex>, где 

<tex>Q = \lbrace \langle q_1, q_2 \rangle | q_1 \in Q_1, q_2 \in Q_2 \rbrace</tex> 

<tex>s = \langle s_1, s_2 \rangle</tex> 

<tex>T = \lbrace \langle t_1, t_2 \rangle | t_1 \in T_1, t_2 \in T_2 \rbrace</tex> 

<tex>\delta (\langle q_1,q_2 \rangle, c) = \langle \delta_1 (q_1),\delta_2 (q_2) \rangle</tex> 
</li>
<li>
<tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}</tex>.

Соответствующий автомат строится как произведение автоматов для языков <tex>L_1</tex> и <tex>\overline {L_2}</tex> 
</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 \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>.
}}

{{Утверждение
|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=st1
|statement=
<tex>L \subset \Sigma_2^*</tex> – регулярный , <tex>\varphi:\Sigma_1^* \rightarrow \Sigma_2^* </tex> – гомоморфизм. Тогда <tex>\varphi^{-1}(L)</tex> – регулярный.
|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> в новом автомате (на том же множестве состояний). Автомат с построенной таким образом функцией переходов, очевидно, распознает слова языка <tex>\varphi^{-1}(L)</tex> и только их.
}}

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

2010-10-08T02:39:53Z