Formal language theory/Homomorphisms

Homomorphisms

Monoid homomorphisms, $h:(S^{*},\cdot )\to (T^{*},\cdot )$, $h(\lambda )=\lambda$ and $h(a\cdot b)=h(a)\cdot h(b)$, can be extended to languages $L\subseteq S^{*}$ in one way that is compatible with set union, $h(L):=\bigcup _{w\in L}h(w)$, to make a basic tool in formal language theory, allowing for renaming and simple replacements of letters.

Special homomorphisms include the non-deleting ones ($h(a)$ is never $\lambda$) and the letter-to-letter ones (the image of each letter is a single letter).

A generalisation of this, the replacement of each letter by a whole language is not in general a homomorphism, it is a substitution.