3622
правки
Изменения
перенесены определения гомоморфизма из другого конспекта
== Базовые определения ==
{{Определение
|definition =
{{Определение
|definition =
'''Слово''' (англ. ''string'' {{---}} ) или ''слово'', 'цепочка'цепочка'') {{---}} конечная последовательность символов некоторого алфавита.
}}
{{Определение
|definition =
Пусть <tex>x, y \in \Sigma^*</tex>. Тогда <tex>xy</tex> обозначает их '''конкатенацию''' (англ. ''concatenation''), т.е. цепочку, в которой последовательно записаны цепочки <tex> x </tex> и <tex> y</tex>.
}}
Множество строк с операцией ''конкатенацияконкатенации'' образует [[Моноид|свободный моноид]].
== Операции над языками ==
* <tex>\{\mathrm{ab, ba, bba, abab, aa}\}a^{-1} = \{\mathrm{b, bb, a}\}</tex>.
== Гомоморфизм языков ==
{{Определение
|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>.
}}
== Ссылки ==
