Prove that is L is regular and h is a homomorphism then hL i

Solution

If L is a regular language, and h is a

homomorphism on its alphabet, then

h(L) = {h(w) | w is in L} is also a regular language.

Proof : Let E be a regular expression for L.

Apply h to each symbol in E.

Language of resulting RE is h(L).

Let h(0) = ab; h(1) =

.Let L be the language of regular expression

01* +10*.

Then h(L) is the language of regular expression

ab* +(ab)*. which can be simplified

* = , so ab*=ab

is the identitiy under concetenation .

so E=E=E for any RE E

Thus ab*+(ab)^* =ab +(ab)^*

=ab+(ab)^*

Finall , L(ab) is contained in L(ab)^*

so RE for h(L) is (ab)^*

^{so h(L) is regular}