Closure IV: Homomorphism

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,

h(L) = {h(w): w L}

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.