Formal language theory/Homomorphisms

Homomorphisms

edit

Monoid homomorphisms,  ,   and  , can be extended to languages   in one way that is compatible with set union,  , to make a basic tool in formal language theory, allowing for renaming and simple replacements of letters.

Special homomorphisms include the non-deleting ones (  is never  ) 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.