String Homomorphism

languages

Definition

String Homomorphism

Let $\Sigma ,\Gamma$ be two alphabet. A homomorphism $h:\Sigma \to {\Gamma }^{\ast }$ is an inductive extension of strings over $\Sigma$:

1. $h(\epsilon )=\epsilon$
2. $\forall w\in {\Sigma }^{\ast }:\forall a\in \Sigma :h(wa)=h(w)\cdot h(a)$

A homomorphism can also be applied to every word on a language $L$:

$$h(L)=\{h(w)\mid w\in L\}$$

Example: Let $h:\{0,1{\}}^{\ast }\to \{a,b{\}}^{\ast }$ a homomorphism with $h(0)=ab$ and $h(1)=\epsilon$. Then $h(0011)=abab$ and $h(L(10^{\ast }1))=L((ab{)}^{\ast })$.