51 51 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 13.2k views answer comment Share Follow Print See all 10 Comments 10 10 Comments reply Show 7 previous comments looser commented Jan 2 reply Follow flag @pavansanTake string "abbaa" . This string contains substring <aa> and also <bb> in it, but still it is rejected by OptionC's machine 3 3 replyShare Siddharth_Perkar commented Jun 21 i edited by Siddharth_Perkar Aug 5 reply Follow flag A DFA has Exactly one outgoing transition for each input symbol from every state.Opt B, S1 has two outgoing transitions for same symbol a , and same for S2 Hence eliminated.Opt C not contains abb/baa Hence eliminated.Opt D not contains aa/bb Hence eliminated. 3 3 replyShare Raj_Dev_Verma commented 5 days ago reply Follow flag Option B is wrong becz it is not dfa Option D is wrong bec its not accecpting the sring genrated by given regular expressions S3 and S4 are equivakent can be minimized So option A is correct 0 0 replyShare Please log in or register to add a comment.
Best answer 38 38 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 2 2 Comments reply Shamim Ahmed commented Oct 23, 2018 reply Follow flag Link not working! 1 1 replyShare Verma Ashish commented Oct 23, 2018 reply Follow flag https://gateoverflow.in/3523/gate2007-it-71 1 1 replyShare Please log in or register to add a comment.
37 37 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 2 2 Comments reply Prateek kumar commented Aug 22, 2016 i edited by Prateek kumar Aug 22, 2016 reply Follow flag right 0 0 replyShare Brij Mohan Gupta commented Nov 2, 2017 reply Follow flag Option C will also not accept baa, abb etc. 2 2 replyShare Please log in or register to add a comment.
9 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 0 reply Please log in or register to add a comment.
3 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 0 reply Please log in or register to add a comment.
0 0 votes (B.) it accepts ab which is not in the language (C.) it is not accepting abb which is in language and also Is false since baa, abb not accepted (D.) it is not accepting aa and bb which is in language coming to option (A.) it accept Sandeep Suri answered Jan 1, 2018 Sandeep Suri comment Share Follow 0 reply Please log in or register to add a comment.
0 0 votes Here, Option B: it generates a string like ab which is not a part of our language, hence rejected. Option C and D: they don't even accept the minimal length strings aa and bb of our language, hence rejected. Option A is thus the right answer! TheAnteamatter answered Jun 20, 2020 TheAnteamatter comment Share Follow See 1 comment 1 1 comment reply Rajsukh Mohanty commented Dec 14, 2024 reply Follow flag C accepts 'aa' and 'bb', but it does not accept strings like 'abb' or 'baa'. 0 0 replyShare Please log in or register to add a comment.
