26
правок
Изменения
→Основные операции
#<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>\overline {L_2}</tex> </p>
</li>
<li><p>
Развернем все переходы назад и поменяем стартовое состояние с терминальными: рассмотрим [[Автоматы_с_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>
