Гомоморфизм регулярных языков

Определение:

Отображение [math]\varphi : \Sigma_1^* \to \Sigma_2^*[/math], сохраняющее операцию конкатенации [math](\varphi(\alpha\beta) = \varphi(\alpha) \varphi(\beta))[/math], называется гомоморфизмом.

Гомоморфизм однозначно задается значениями на алфавите: [math]\varphi(\overline{c_1 c_2 \ldots c_k}) = \varphi(c_1) \varphi(c_2)\ldots \varphi(c_k)[/math].

Определение:

Образом языка [math]L \subset \Sigma_1^*[/math] при гомоморфизме [math]\varphi: \Sigma_1^* \rightarrow \Sigma_2^*[/math] называется язык [math]\varphi (L) \overset{\underset{\mathrm{def}}{}}{=} \lbrace \varphi (x) | x \in L \rbrace[/math].

Определение:

Прообразом языка [math]L \subset \Sigma_2^*[/math] при гомоморфизме [math]\varphi: \Sigma_1^* \rightarrow \Sigma_2^*[/math] называется язык [math]\varphi^{-1} (L) \overset{\underset{\mathrm{def}}{}}{=} \lbrace x | \varphi (x) \in L \rbrace[/math].