# TOC Doubt

1 vote
229 views
Write the Regular Expression in which two a's should not come together?

Please tell how to write this R.E in a step by step way, thanks!

1 vote

Strings in the language will be
eps, a, b, ab,ba,bb,aba,bba,abb, bbbb,abbb,abab,abba...

First make DFA, and then convert into regular expression:

=$(b + ab)^{*}(eps+a)$

edited
2

your dfa is correct but Regular expression is not correct, it is not accepting "bbbbbba"

correct regular expression will be (b + ab)*(a + epsilon)

0

Well, the correct R.E is (b+ab)*(epsilon+a)

or

(a+epsilon)(b+ba)*

0
Yes, you're right, but how did you get this, @joshi_nitish
0
draw DFA, which manu has drawn correctly, than apply state elimination method to get corresponding regular expression..
0
Okay, I'll see, Sir, thanks!
0
yes, corrected!
0
welcome,
btw i am not sir..
0

joshi_nitish @manu00x Can you please tell, how to deal with 2 final states, I'm not getting around how to deal with final state B when I apply state elimination method. Can you please post a photo?

0
in my case i don't follow any particular algorithm to solve these questions, if there are two final states or more you can resolve the loop at any one state.
For example A contains two loops one is because of 'b' and second is because of ab.
$(b + ab)^{*}$ now see how can we reach final state either by fixing eps or a, language will be accepted
so overall expression comes to $(b + ab)^{*}(eps +a)$
if you want you can resolve loops on the second final state also!
0
Jo C state hai, woh Dead state hai na? Uska kuch nai karna, right?
1
DFA takes care of member and non-members both, while regular expression and grammar consider only members of the language.

## Related questions

1
142 views
Construct a minimal DFA which accepts set of all strings over {a,b}, such that $1)$Second symbol from $RHS$ should be $‘a’$ $2)$Third symbol from $RHS$ should be $‘a’$
1 vote
why $bb^*$ is $b^*$ and not $b^+$? Ref: $a^*(bb^*a + a)a^*\\=a^*(bb^*+\epsilon)aa^*\\=a^*b^*aa^*\\=a^*b^*a^*a$