Question

We proved in class that for a homomorphism h : Σ ∗ → Γ ∗, if A ⊆ Σ ∗ is a regular set, then h ( A )is also regular. We proved this by letting α be a regular expression such that A = L ( α ). Then we defined α ′ for all regular expressions α over Σ ∗ by replacing each alphabet symbol a that appears in α by h ( a ), and used structural induction on the regular expression α ′ to show L ( α ′ ) = h ( L ( α ) ) (Theorem 10.2). If the structure of α is such that α = β γ (that is, it is the concatenation of two smaller regular expressions) , and we assume the inductive hypothesis that L ( β ′ ) = h ( L ( β ) ) and similarly L ( γ ′ ) = h ( L ( γ ) ), show that L ( ( β γ ) ′ ) = h ( L ( β γ ) ).

Answer 1

A homomorphism on Σ is a function h : Σ∗ → Θ∗ , where Σ and Θ are alphabets. Let w = a1a2 · · · an ∈ Σ∗ . Then h(w) = h(a1)h(a2) · · · h(an) and h(L) = {h(w) : w ∈ L} Example: Let h : {0, 1} ∗ → {a, b} ∗ be defined by h(0) = ab, and h(1) = . Now h(0011) = abab. Example: h(L(10∗1)) = L((ab) ∗).

Let h(w) ∈ L, and suppose w /∈ L((ba) ∗). There are four cases to consider. 1. w begins with a. Then h(w) begins with 01 and ∈/ L((00 + 1) ∗). 2. w ends in b. Then h(w) ends in 10 and ∈/ L((00 + 1) ∗). 3. w = xaay. Then h(w) = z0101v and ∈/ L((00 + 1) ∗). 4. w = xbby. Then h(w) = z1010v and ∈/ L((00 + 1) ∗).