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)*