clouser property of regular language

Question

What is the difference between substitution property, homomorphism property and inverse homomorphism property?

Give an example to best support your answer.

Answer 1

Let's take Σ={a, b} and Γ={0, 1}.

Now let h be a homomorphism function where h_Σ=>Γ*

Let's take an example to better understand this. 

Let L={aa, ba, b} be a finite regular language now given h(a)=00, h(b)=10

Now we have to find h(L)?

Just substitute 00 in the place of a whereever in L and 10 in place of b.

We get, h(L)={0000, 0100, 10}

See that |L| =3 and |h(L)| =3, therefore |L|=|h(L)| in this example but this is not always true. Sometime there may arrive some duplicates h(L) while substution but we can guarantee that |h(L)| <= L

Let's take an example for inverse homomorphism as the name suggests we have to do reverse of homomorphism

Let L={0101} be a finite regular language now given h(a)=0, h(b)=1, h(c)=01

Now we have to find h^-1(L)?

Just substitute a in the place of 0 whereever in L and b in place of 1 and c in place of 01.

We get, h^-1(L)={abab,  abc, cab, cc}

See that there are total 4 possible combinations and  |L| =1 and |h^-1(L)| =4, therefore we cannot guarantee that |h(L)| <= |L| or |h(L)| >= |L|