search
Log In
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!
in Theory of Computation 229 views

1 Answer

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

0 votes
1 answer
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’$
asked Dec 27, 2018 in Theory of Computation Lakshman Patel RJIT 142 views
1 vote
0 answers
2
156 views
why $bb^*$ is $b^*$ and not $b^+$? Ref: $a^*(bb^*a + a)a^*\\=a^*(bb^*+\epsilon)aa^*\\=a^*b^*aa^*\\=a^*b^*a^*a$
asked Dec 4, 2017 in Theory of Computation Tuhin Dutta 156 views
6 votes
3 answers
3
904 views
I'm so confused what happens when you concatenate/MUL Epsilon ε with any input symbol? What is ε.a = ? and what is ε.0 = ? what is ε.1= ?
asked Aug 11, 2017 in Theory of Computation iarnav 904 views
0 votes
1 answer
4
488 views
How many 2 state DFA’s with designated initial state can be constructed over the alphabet Σ = {a, b} that accept empty language ϕ ? (a) 4 (b) 16 (c) 20 (d) 24
asked May 22, 2019 in Theory of Computation Hirak 488 views
...