Q1. Show that the following pairs of regular expressions define the same language over the alphabet
L = {p, q}.
(i) (pq)p and p(qp)
(ii) (p* + q)* and (p + q)*
(iii) (p* + q*)* and (p + q)*
[15 marks = 5*3]
Solution:
(i) (pq)p and p(qp) represents same language.
Both will never generate pp’s and both are starting and ending with p
(ii) (p* +q)* (p+q)*
(p*)+ q p* + q*
p* + q* p* + q*
Both are all strings possible in L = {p,q}
(iii) (p* +q*)* (p+q)*
(p*)* + (q*)*
p* + q*
(p + q)* Language with all strings
Q2. Write a regular expression for the following language over the alphabet L = {x, y} such that it accepts all strings in which the letter y is never tripled. This means that no word contains the substring yyy. [5 marks]
Solution:
The required R.E will be
(˄ + y + yy) (x + xy + xyy)*
If you want to know how you can join us and get 100% Discount on your FEE ask Cyberian in Chat Room!
