Suppose and
are alphabets (not necessarily distinct). Then a *homomorphism* h is a
function from to *.

If w is a string in , then we define h(w) to be the string obtained by replacing each symbol x by the corresponding string h(x) *.

If L is a language on ,
then its *homomorphic image* is a language on .
Formally,

**Theorem.** If L is a regular language on ,
then its homomorphic image h(L) is a regular language on .
That is, if you replaced every string w in L with h(w), the resultant set of
strings would be a regular language on .

**Proof.**

- Construct a dfa representing L. This is possible because L is regular.
- For each arc in the dfa, replace its label x with h(x) .
- If an arc is labeled with a string w of length greater than one, replace the arc with a series of arcs and (new) states, so that each arc is labeled with a single element of . The result is an nfa that recognizes exactly the language h(L).
- Since the language h(L) can be specified by an nfa, the language is regular. Q.E.D.

Copyright © 1996 by David Matuszek

Last modified Feb 13, 1996