Изменения
→Прямой и обратный гомоморфизмы
==Прямой и обратный гомоморфизмы==
{{Определение
|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> и только их.
}}
