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