CS402 Assignment 1 solution 2020 with Download File

Solution of thoery of automata also here.

CS402 ASSIGNMENT 1 SOLUTION 2020

Q1. Show that the following pairs of regular expressions define the same language over the alphabet.

L = {p,q}.

1.       (pq)*p  and p(qp)*

2.       (p* + q)* and (p + q)*

3.       (p* + q*)* and (p+q)*

1.       (pq)*p  and p(qp)*

Let L1 = (pq)*p

L1 = {p, pqp, pqpqp, pqpqpqp, pqpqpqp….}

L2 = p(qp)*

L2 = {p, pqp, pqpqp, pqpqpqp, pqpqpqp….}

Hence the both RE have the same language over the alphabet p and q.

2.       (p* + q)* and (p + q)*

Let L1 = (p*+q)*

L1 = {ꓥ,p,q,pq,qqp,ppq,….}

L2 = (p+q)*

L2 = {ꓥ,p,q,pq,qqp,ppq,…}

Hence the both RE have the same language over the alphabet p and q.

3.       (p* + q*)* and (p+q)*

L1 = {p* + q*}*

L1 = {ꓥ,p,q,pq,ppqq,pppqqq,ppppqqqq…}

L2 = (p+q)*

L2 = {ꓥ, p,q,pq,ppqq,pppqqq,ppppqqqq…}

Hence the both RE have the same language over the alphabet p and q.

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 mean that no word contains the substring yyy.

Ans:

X*(y+yy)x*

= {xy,yxx,yyx,yxxx,xxxyy,yxxxx…}