3622
правки
Изменения
Нет описания правки
#<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=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> и только их.
