1 votes 1 votes 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! Theory of Computation theory-of-computation finite-automata + – iarnav asked Aug 10, 2017 iarnav 769 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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) $ Manu Thakur answered Aug 10, 2017 • edited Aug 10, 2017 Manu Thakur comment Share Follow See all 11 Comments See all 11 11 Comments reply joshi_nitish commented Aug 10, 2017 reply Follow Share your dfa is correct but Regular expression is not correct, it is not accepting "bbbbbba" correct regular expression will be (b + ab)*(a + epsilon) 2 votes 2 votes iarnav commented Aug 10, 2017 reply Follow Share Well, the correct R.E is (b+ab)*(epsilon+a) or (a+epsilon)(b+ba)* 0 votes 0 votes iarnav commented Aug 10, 2017 reply Follow Share Yes, you're right, but how did you get this, @joshi_nitish 0 votes 0 votes joshi_nitish commented Aug 10, 2017 reply Follow Share draw DFA, which manu has drawn correctly, than apply state elimination method to get corresponding regular expression.. 0 votes 0 votes iarnav commented Aug 10, 2017 reply Follow Share Okay, I'll see, Sir, thanks! 0 votes 0 votes Manu Thakur commented Aug 10, 2017 reply Follow Share yes, corrected! 0 votes 0 votes joshi_nitish commented Aug 10, 2017 reply Follow Share welcome, btw i am not sir.. 0 votes 0 votes iarnav commented Aug 10, 2017 reply Follow Share @ 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 votes 0 votes Manu Thakur commented Aug 10, 2017 i edited Aug 10, 2017 reply Follow Share 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 votes 0 votes iarnav commented Aug 10, 2017 reply Follow Share Jo C state hai, woh Dead state hai na? Uska kuch nai karna, right? 0 votes 0 votes Manu Thakur commented Aug 10, 2017 reply Follow Share DFA takes care of member and non-members both, while regular expression and grammar consider only members of the language. 1 votes 1 votes Please log in or register to add a comment.