Question

9. Which of the following are true for all regular languages and all homomorphisms? (a) h (L1 ∪ L2)= h (L1) ∩ h (L2). (b) h (L1 ∩ L2)= h (L1) ∩ h (L2). (c) h (L1L2) = h (L1) h (L2).

Answer 1

Answer:

h (L1 ∪ L2)= h (L1) ∩ h (L2).

This is true.

There will be w ∈  (L1 ∪ L2) for any s ∈ h (L1 ∪ L2) in such a way that s=h(w)

we can assume that w ∈ L1

So In this case h(w) ∈ L (S1). Hence s ∈ L(S1)

for any s ∈ h (L1) U h(L2)

We can assume that s ∈ L(S1)

There exists w ∈ L1 such that s= h(w)

In this case it is w ∈ L1 U L2 as well.

Hence , s ∈ h (L1 U L2)

Explanation

consider  = 0,1 and  = a,b and h(0) = a , h(1) = ab

(a) Consider L1 = 10,01 and L2 = 00,11

   Now L1 ∪ L2 = 00,01,10,11

   h (L1 ∪ L2) = h(00) , h(01) , h(10) , h(11) = h(0)h(0) , h(0)h(1) , h(1)h(0) , h(1)h(1)

  = aa, aab , aba , abab

Hence h (L1 ∪ L2) = aa, aab , aba , abab .

Here h (L1) = h(10) , h(01) = h(1)h(0) , h(0)h(1) = aba , aab

Hence h (L1) = aba , aab .

Here h (L2) = h(00) , h(11) = h(0)h(0), h(1)h(1) = aa, abab

Hence h(L2) = aa, abab.

Finally Hence , h (L1 ∪ L2)= h (L1) ∩ h (L2).