edited by
1,570 views
2 votes
2 votes
Let L be a language defined as follows:
L={w∈{a,b}* | every two a^' s in w are separated by even number of b' s}

a)(bb)* a(bb)* a(bb)*+ϵ

b) (b* a(bb)* ab*)*

c) (b+abb)* (ϵ+ab)*

d)none of the above

 

  the answer is none of the above .. but i have confusion regarding , what will be the correct RE?

________________________________________________________________________
ok there is a bit of a confusion regarding whether b can take value 0 or not ..

i think  we can take b=0 ,. but i want to know .. what if b>0 .

which actually makes more sense since they are asking about "separation" of two a's.
edited by

3 Answers

Best answer
1 votes
1 votes
I am answering my own question because i want someone to verify the answer .

i am quiet convinced that this is the RE:

b* + b*a(b(bb)*ba)* + b*a(b(bb)*ba)* b (bb)* + b*a(b(bb)*ba)* b(bb)* b
selected by
1 votes
1 votes

Answer is d) 

a)  {aa} can be generated from this RE.

again for b) we can generate {aa}

c)   {abab} can be generated which is not as per the language L.

for b>=0, RE will be

b*(bb+a(bb)*)*(a+Є)(b+Є)

edited by
1 votes
1 votes

This is the dfa, but i am unable to derive a reEx as i am pretty bad at ardens theorm :P

Related questions

0 votes
0 votes
1 answer
2
1 votes
1 votes
2 answers
3
Ashish Roy 1 asked Sep 27, 2018
2,071 views
Given two Regular expressions are equal or not ?1) (1+01*0)* 2) 1*(01*0)* 1*Give proper explanation also.
1 votes
1 votes
0 answers
4