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