Homo Morph Isms Of Regular Languages

Homomorphisms of Regular Languages Chris Johnson September 19, 2007 Suppose Σ1 and Σ2 are alphabets and that f : Σ∗1 → Σ∗2 is a homomorphism; ∀x, y ∈ Σ∗1 : f (xy) = f (x)f (y). We wish to show that L1 ⊆ Σ∗1 is a regular language if and only if f (L1 ) = L2 is a regular language. Assume L1 ⊆ Σ∗1 is a regular language, then the set of equivalence classes of distinguishable strings of L1 is finite. Suppose x and y are members of the same equivalence class in L1 ; x and y are indistinguishable in L1 . This means that for every z ∈ Σ∗1 , xz ∈ L1 if and only if yz ∈ L1 . Consider the images of xz and yz under f . Now suppose there exists a z ∈ Σ∗2 such that f (x) and f (y) are distinguishable in L2 ; f (x)z ∈ L2 , and f (y)z ∈ / L2 . The fact that f (x)z ∈ L2 means there is some string in L1 that maps to f (x)z, f −1 (f (x)z). We note that as x maps to f (x) and f is a homomorphism, there must be some string f −1 (z) in L1 that maps to z; f −1 (z) exists and f −1 (f (x)z) = xf −1 (z) ∈ L1 . However, x and y are indistinguishable in L1 which gives the following. xf −1 (z) ∈ L1 ⇒ yf −1 (z) ∈ L1 ⇒ f (yf −1 (z)) = f (y)z ∈ L2 However this contradicts our earlier assumption that f (y)z ∈ / L2 , thus no such z exists. From this we conclude that if x and y are indistinguishable in L1 , f (x) and f (y) are indistinguishable in L2 , and so the number of equivalence classes of distinguishable strings in L2 can not be greater than the number of equivalence classes of distinguishable strings in L1 . Since there are only finitely many such classes in L1 , there are only finitely many in L2 , and so L2 is regular. Now we assume that f (L1 ) = L2 is a regular language. Let y ∈ L2 and consider f −1 (y), the set of all strings in L1 that map to y. Assume this set looks as follows. f −1 (y) = {x1 , x2 , ...} Pick two distinct elements xi , xj ∈ f −1 (y) and assume xi and xj are distinguishable in L1 ; there exists a z such that xi z ∈ L1 and xj z ∈ / L1 . This gives the following. f (xi z) = = f (xj z) = =

f (xi )f (z) yf (z) ∈ L2 f (xj )f (z) yf (z) ∈ L2 1

However yf (z) ∈ L2 contradicts our assumption that xj z ∈ / L1 , and so no such z can exist. This tells us that everything in L1 that maps to y is indistinguishable in L1 . Now assume that y1 and y2 are indistinguishable strings in L2 (∀z ∈ Σ∗2 : y1 z ∈ L2 ⇔ y2 z ∈ L2 ) and assume x1 , x2 ∈ L1 such that f (x1 ) = y1 , f (x2 ) = y2 . Suppose there is a z ∈ L1 such that x1 z ∈ L1 and x2 z ∈ / L1 . This gives us the following. x1 z ∈ L1 ⇒ f (x1 z) = f (x1 )f (z) = y1 f (z) ∈ L2 x2 z ∈ / L1 ⇒ f (x2 z) = f (x2 )f (z) = y2 f (z) ∈ / L2 But y1 and y2 are indistinguishable, so this is a contradiction and no such z exists. This tells us that if y1 and y2 are indistinguishable in L2 , the elements of their inverses are indistinguishable from one another in L1 . This, together with the previous result, implies the number of equivalence classes of distinguishable strings in L1 is finite the number of such classes is finite in L2 , thus L1 is regular if L2 is regular. We have shown, from a purely theoretic, language-based perspective (as opposed to a “constructive” perspective in which we construct a finite automaton or regular expression) that given a homomorphism f , the language L is regular if and only if f (L) is also regular.

2