UGC NET Computer Science December 2019 | Question 96

Question 96

---

Consider Σ = {w, x} and T = {x, y, z}. Define homomorphism h by :
h(x) = xzy
h(w) = zxyy
If L is the regular language denoted by r=(w+x*)(ww)*. then the regular language h(L) is given by

1. (1) (zxyy + xzy) (zxyy)
2. (2) (zxyy +(xzy)*) (zxyy zxyy)*
3. (3) (zxyy + xzy )(zxyy)*
4. (4) (zxyy + (xzy)*) (zxyy zxyy)

Answer : (2) (zxyy +(xzy)*) (zxyy zxyy)*

Explanation

If L is the regular language denoted by r = (w+x*)(ww)*.
Here its given that homomorphism h is defined by :
h(x) = xzy
h(w) = zxyy
Now, to derive h(L) we replace the x by xzy and w by zxyy in above regular expression.
then the regular language h(L) is (zxyy +(xzy)*) (zxyy zxyy)*

Homomorphism
A homomorphism on an alphabet is a function that gives a string for each symbol in that alphabet domain. Simply, We can say in homomorphism we replace each letter in a language with another letter in some other language.

DEFINITION: A homomorphism is a kind mapping h for some alphabet in the domain Σ ∗. Where Σ will preserve the concatenation.
∴ h(v · w) =h(v) · h(w).

Let E be a regular expression for L.
Apply h to each symbol in E.
Language of resulting Regular Expression is h(L).

Example:
Let h(0) = ab; h(1) = c.
Let L be the language of regular expression 01* + 10*.
Now, to derive h(L) we replace the 0 by ab and 1 by c in above regular expression.
Then h(L) is the language of regular expression abc* + c(ab)*.

So, option 2 is correct answer.

Previous	Next
UGC NET CS December 2019 - Question 95	UGC NET CS December 2019 - Question 97