retagged by
754 views
0 votes
0 votes

Show that the following pairs of regular expressions define the same language over the alphabet I = [a, b].

s(a) p(pp)*( A + p)q + q and p*q

(b) A +0(0+1)* + (0+1)* 00(0+1)* and ((1*0)*01*)*

(c) (s*ttt)*s* and s*(ttts*)*

retagged by

1 Answer

0 votes
0 votes
Take here A as epsilon

C) By shifting rule (r1.r2)*.r1 = r1(r2.r1)*.

(s*ttt)*s* and s*(ttts*)* are defining same language

B) A +0(0+1)* + (0+1)* 00(0+1)*  defining the language with atleast 2 zeroes but ((1*0)*01*)* it is not ( 10 is not acceptable)

A) p(pp)*( A + p)q + q  for this language L ={q,ppq,pppq,.....}.  p*q for this language L={q,pq,ppq,…} those two are not equal.

So c only have the pair of regular expression s define the same language

Related questions

0 votes
0 votes
2 answers
2