Изменения

Пусть <tex>x, y \in \Sigma^*</tex>. Тогда <tex> x \cdot y </tex> или <tex>xy</tex> обозначает их '''конкатенацию''' (англ. ''concatenation''), т.е. цепочку, в которой последовательно записаны цепочки <tex> x </tex> и <tex> y </tex>.

|definition='''Гомоморфизмом цепочекязыков''' называется отображение <tex>\varphi : \Sigma_1^* langle L_1, \to cdot \Sigma_2^*rangle </tex>, действующее следующим образом: и <tex>\varphi(\overline{c_1 c_2 \ldots c_k}) = \varphi(c_1) \varphi(c_2)\ldots \varphi(c_k)</tex>.}}Таким образом, гомоморфизм цепочек сохраняет операцию конкатенацииlangle L_2, а именно: <tex> \varphi(\alpha\beta) = \varphi(\alpha)\varphi(cdot \beta) </tex>. {{Определение|definition='''Гомоморфизмом языков''' <tex> L_1 </tex> и <tex> L_2 rangle </tex> называется отображение <tex>\Phi : \colon L_1 \to L_2</tex> такое, что <tex> \Phi(L_1) = \{\varphi(x) | x \in L_1 \} = L_2 </tex>, где <tex> \varphi </tex> {{---}} ''гомоморфизм цепочек''.}} {{Определение|definition='''Образом языка''' <tex>L \subset colon \Sigma_1^*</tex> при гомоморфизме <tex>\varphi: \Sigma_1^* \rightarrow \Sigma_2Sigma^{*</tex> называется язык <tex>\varphi (L) \overset{\underset{\mathrm{def}}_{}}{=1} \lbrace to \varphi (x) | x \in L \rbrace</tex>.}}{Sigma^{Определение|definition='''Прообразом языка''' <tex>L \subset \Sigma_2^*</tex> при гомоморфизме <tex>\varphi: \Sigma_1^* \rightarrow \Sigma_2^*</tex> называется язык <tex>\varphi^{-1} (L) \overset{\underset{\mathrm{def}}{}}_{=2} \lbrace x | \varphi (x) \in L \rbrace</tex>.