Изменения

Перейти к: навигация, поиск
Прямой и обратный гомоморфизмы
Гомоморфизм однозначно задается значениями на алфавите: <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> и только их.
}}
26
правок

Навигация