[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 sigma and gamma are alphabets (not necessarily distinct). Then a homomorphism h is a function from sigma to gamma*.

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

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

h(L) = {h(w): w is a member of L}

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

Proof.


Copyright 1996 by David Matuszek
Last modified Feb 13, 1996