42 votes 42 votes Consider the regular expression $R = (a + b)^* (aa + bb) (a + b)^*$ Which deterministic finite automaton accepts the language represented by the regular expression $R$? Theory of Computation gateit-2007 theory-of-computation finite-automata normal + – Ishrat Jahan asked Oct 30, 2014 • edited May 1, 2019 by Pooja Khatri Ishrat Jahan 8.0k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply raja11sep commented Dec 19, 2021 reply Follow Share B → “ab” C → “abb” D → “aa” 1 votes 1 votes ꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ commented Oct 20, 2023 reply Follow Share B is still not a DFA coz of by the definition Dfa We can have exctly one transition from one state to any other state, but here in S3 there are 2 transitions on a which is not valid. 0 votes 0 votes Gopal Deshmuk commented Oct 21, 2023 reply Follow Share What is the proper way of solving these type of questions? Is trial and error the only way? 0 votes 0 votes ꧁༒☬ĿọŗԀ 🆂🅷🅸🆅🅰☬༒꧂ commented Oct 22, 2023 reply Follow Share @Gopal Deshmuk take strings which is accepting by the regular expression and check which string is accepted by the dfa is the easiest way . 1 votes 1 votes Please log in or register to add a comment.
Best answer 30 votes 30 votes DFA given in option A Here, $S_3$ and $S_4$ are equivalent states and can be minimized. This results in DFA given in: https://gateoverflow.in/3523/gate2007-it_71 Praveen Saini answered Mar 2, 2015 • edited Jun 15, 2018 by Milicevic3306 Praveen Saini comment Share Follow See all 2 Comments See all 2 2 Comments reply Shamim Ahmed commented Oct 23, 2018 reply Follow Share Link not working! 1 votes 1 votes Verma Ashish commented Oct 23, 2018 reply Follow Share https://gateoverflow.in/3523/gate2007-it-71 1 votes 1 votes Please log in or register to add a comment.
30 votes 30 votes C. Is false since abb not accepted D. Is false since as or bb not accepted B.is false since it is not DFA A. Is the ans .. S3 and S4 are similar States..minimum no.of states are 4 papesh answered Aug 6, 2016 papesh comment Share Follow See all 2 Comments See all 2 2 Comments reply Prateek kumar commented Aug 22, 2016 i edited by Prateek kumar Aug 22, 2016 reply Follow Share right 0 votes 0 votes Brij Mohan Gupta commented Nov 2, 2017 reply Follow Share Option C will also not accept baa, abb etc. 2 votes 2 votes Please log in or register to add a comment.
9 votes 9 votes A) as it accepts anything (aa or bb )anything So aa ,bb, aaa,aaaa bbb,bbbb,bbbbbb,bbaaaababba ababababaababababa or abababababbb will be accepted and only A satisfies. Correct if Wrong, Abhinav Rana answered Dec 19, 2014 Abhinav Rana comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes lets try by elimination: (B.) it accepts ab which is not in language (C.) it is not accepting abb which is in language (D.) it is not accepting aa which is in language coming to option (A.) it accepts anything containing aa/bb mint answered Feb 3, 2017 mint comment Share Follow See all 0 reply Please log in or register to add a comment.