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).

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).