Материал из Викиконспекты
|
|
| Строка 1: |
Строка 1: |
| − | {{Определение
| |
| − | |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>.
| |
| − | }}
| |
| − |
| |
| − | [[Категория: Теория формальных языков]]
| |
| − | [[Категория: Автоматы и регулярные языки]]
| |
Версия 17:25, 9 ноября 2013
