[Overview] [Previous] [Next]

# Closure IV: Homomorphism

Note: "Homomorphism" is a term borrowed from group theory. What we refer to as a "homomorphism" is really a special case.

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.