The Gateway to Computer Science Excellence
0 votes
116 views

Consider this regular expression:  r = (a*b)* + (b*a)*


This is equivalent to


(a) (a + b)*

(b) (a + b)* · (ab)+ + (a + b)* (ba)+


(c) (a + b)*a + (a + b)* b

(d) None of above

in Theory of Computation by (365 points)
edited by | 116 views
+1
a should be answer ...as eplison is generated by r and a ..and other strings too ..
0
but how aaba string is generated from  r
0
from (b* a)* ===> take 3 times

1) a by taking b* = ∈

2) a by taking b* = ∈

3) ba by taking b* = b
0
tq
0
i think option (d) is correct .ababa is not in the language but can be generated by option (a) so none of these is coorect option.
0

hi .. look at this :

in option B) just consider second part ...that is   (a + b)* (ba)+

now (a+b)^3(ba)+ gives us =(a+b)(a+b)(a+b)(ba) now i have option that from first 3 brackest i can take a or b as per my wish ..so 

take a form 1st b from second and a agian from 3rd so we get (ababa)...so string generated, similarily you can take First part of C option and cross check that same string can also be genertaed by option C.

 

0
is ababa is in original language??????can you generate it  from original language???
0
Yes you can generate ababa from given language
0
how?????
0

take second part of r

that is ((b*a)*

now take b* as episolon = (b^0 .a)(b^1a)(b^1a)...generated form it.

0
oh its my mistake.but option(a) is not correct.
0
a is correct bro ...it generates strings with alpahabets a and b with Epsilon too ..

while b and c also generate same except that they failed to generate epsilon.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,297 answers
198,265 comments
104,978 users