Define homomorphism with an example. Prove that h(L) is regular, if L is a regular language over alphabet Σ and h is a homomorphism on Σ.


Homomorphism: A string homomorphism is a function on string that works by substituting a particular string for each symbol, such that h (a) contains a single string for each a. We generally take h(a) to be the string itself rather then the set containing that string.
Example: 
Let, h(0) = ab
h(1) = ϵ
then (0011) = ababϵϵ
= abab

Proof: Let, L = L(R) for some regular expression R. In general, if E is a regular expression with symbols in Σ, let h(E) to the expression we obtain by replacing each symbol a of Σ in E by h(a). We claim that h(R) defines the language h(L).
In structural induction that we take a sub-expression E of R and apply h to it to get h(E), the language of h(E) is the same language we get if we apply h to the language L(E). Formally,
L(h(E)) = h(L(E))

Basis: It E is ϵ or ∅, then h(E) is the same as E, since h does not affect the string ϵ or the language ∅. Thus, L(h(E)) = L(E).
However, if E is ∅ or ϵ, then L(E) contains either no strings or a string with no symbols, respectively. Thus h(L(E)) = L(E) in either case. We conclude L(h(E)) = L(E) = h(L(E)).
The only other basis case is if E = a for some symbol a in Σ. In this case, L(E) = {a}, so h(L(E)) = {h(a)}. Also h(E) is the regular expression that is the string of symbols h(a). Thus, L(h(E)) is also {h(a)}, and we conclude L(h(E)) = h(L(E)).

Induction: There are three cases, each of them simple. We shall prove only the union case, where E = F + G. The way we apply homomorphisms to regular expressions assures us that h(E) = h(F + G) = h(F) + h(G).
We also know that, L(E) = L(F) ∪ L(G) and
L(h(E)) = L(h(F) + h(G) = L(h(F)) ∪ L(h(G))   ---   (i)
bu the definition of what “+” means in regular expressions finally,
h(L(E)) = h(L(F) ∪ h(G)) = h(L(F)) ∪ h(L(G))   ---   (ii)
because h is applied to a language by application to each of its strings individually. Now we may invoke the inductive hypothesis to assert that L(h(F)) = h(L(F)) and L(h(G)) = h(L(G)).
Thus, the final expression in (i) and (ii) are equivalent and therefore so are their respective first terms, that is L(h(E)) = h(L(E)).
We shall not prove the cases where expression E is a concatenation or closure; the ideas are similar to the above in both cases. The conclusion is that L(h(R)) is indeed h(L(R)); i.e. applying the homomorphism h to the regular expression for Language L results in a regular expression that defines the language h(L).


No comments

Dear Members, Thanks for Your Comments. We must be reply your comment answer as soon as possible. Please Stay with us.....

Theme images by ideabug. Powered by Blogger.