26
правок
Изменения
м
----
При доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и автоматных языков. Пусть языки <tex>L_1, 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> соответственно.
----
4. Инвертируем множество допускающих состояний: рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , \delta_1 : Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle </tex>. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>.
Автомат для пересечения языков можно построить явно<ol start="4"><li><p>Инвертируем множество допускающих состояний: рассмотрим автомат <tex>A_1' = \langle \Sigma , Q_1 , s_1 , Q_1 \setminus T_1 , используя конструкцию пересечения автоматов\delta_1 :Q_1 \times \Sigma \rightarrow 2^{Q_1} \rangle </tex>. Очевидно, он допускает те и только те слова, которые не допускает автомат <tex>A_1</tex>.<br/>При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить и сделать допускающим.</p></li>
→Доказательство
===Доказательство===
Свойства 1,2,3 непосредственно следуют из определения регулярных языков.
При таком построении следует помнить, что если в исходном автомате было опущено дьявольское состояние, его нужно явно добавить доказательстве дальнейших свойств воспользуемся эквивалентностью регулярных и сделать допускающимавтоматных языков.----5. Следует из пунктов 1 Пусть языки <tex>L_1</tex> и 4, т.к. <tex>L_1 \cap L_2 </tex> распознаются автоматами <br /> <tex>A_1 = \overline{langle \Sigma , Q_1 , s_1 , T_1 , \delta_1 : Q_1 \times \Sigma \overlinerightarrow 2^{L_1Q_1} \cup rangle </tex> и <tex>A_2 = \langle \Sigma , Q_2 , s_2 , T_2 , \delta_2 : Q_2 \times \overlineSigma \rightarrow 2^{L_2}Q_2}\rangle </tex>соответственно.
<li><p>Следует из пунктов 1 и 4, т.к. <tex>A L_1 \cap L_2 = \langle overline{\Sigma , Q , s , T , overline{L_1} \delta : Q cup \times \Sigma \rightarrow 2^overline{QL_2}} \rangle </tex>, где. <br/>
Автомат для пересечения языков можно построить явно, используя конструкцию пересечения автоматов: <tex/p>Q = \lbrace \langle q_1, q_2 \rangle | q_1 \in Q_1, q_2 \in Q_2 \rbrace</texp>
<tex>s A = \langle s_1\Sigma , Q , s , T , s_2 \delta : Q \times \Sigma \rightarrow 2^{Q} \rangle</tex>, где <br/>
<tex>T Q = \lbrace \langle t_1q_1, t_2 q_2 \rangle | t_1 q_1 \in T_1Q_1, t_2 q_2 \in T_2 Q_2 \rbrace</tex> <br/>
<tex>\delta (\langle q_1,q_2 \rangle, c) s = \langle \delta_1 (q_1)s_1,\delta_2 (q_2) s_2 \rangle</tex>----6. <tex>L_1 \setminus L_2 = L_1 \cap \overline{L_2}<br/tex>.
<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 (q_1),\delta_2 (q_2) \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>
