Question

Prove that is L is regular and h is a homomorphism, then h(L) is regular.

Answer 1

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}