3 votes 3 votes The number of states in minimal DFA for strings starting with $ab^{2}$ and ending with $b$ over the alphabet $\left \{ a,b \right \}$ is__________. // doubt: minimal string should be $ abb $ right? Theory of Computation theory-of-computation number-of-states minimal-state-automata + – Devwritt asked Dec 13, 2018 • edited Dec 13, 2018 by srestha Devwritt 1.5k views answer comment Share Follow See all 23 Comments See all 23 23 Comments reply srestha commented Dec 13, 2018 reply Follow Share NFA should be $abb\left ( a+b \right )^{*}b$ 0 votes 0 votes Satbir commented Dec 13, 2018 reply Follow Share String abb would be accepted or not ? I think there will be 2 final states in dfa one for accepting abb and other for accepting abb(a+b)∗b 0 votes 0 votes Devwritt commented Dec 14, 2018 reply Follow Share @srestha but in 'abb' string is ending with b right, they didn't mentioned about length should be 4 at least 0 votes 0 votes srestha commented Dec 14, 2018 reply Follow Share yes trivial case abb 0 votes 0 votes shreyansh jain commented Dec 19, 2018 i edited by shreyansh jain Dec 19, 2018 reply Follow Share 6 states are required. 0 votes 0 votes Utkarsh Joshi commented Dec 19, 2018 i edited by Utkarsh Joshi Dec 19, 2018 reply Follow Share It should be 6. 1 votes 1 votes Utkarsh Joshi commented Dec 19, 2018 i edited by Utkarsh Joshi Dec 19, 2018 reply Follow Share chk this 1 votes 1 votes Ramij commented Dec 19, 2018 reply Follow Share But their answer is 6,, they didn't consider abb as accepting string. 0 votes 0 votes shreyansh jain commented Dec 19, 2018 reply Follow Share @Utkarsh Joshi DFA doesn't seem correct to me.Try for $abbaab$ which is a valid string. 1 votes 1 votes Utkarsh Joshi commented Dec 19, 2018 reply Follow Share yes shreyansh jain 0 votes 0 votes Utkarsh Joshi commented Dec 19, 2018 reply Follow Share edited! 0 votes 0 votes kumar.dilip commented Dec 19, 2018 reply Follow Share Answer will be 6. The minimum string is abbb which required 5 states. ===>>>put (a+b)^* between the last two b's. ===>> one dead state. 5 + 1 = 6. 0 votes 0 votes Ramij commented Dec 19, 2018 reply Follow Share Why minimum string is abbb ,, why abb is not accepted???? 0 votes 0 votes Utkarsh Joshi commented Dec 19, 2018 reply Follow Share Ramij it will be accepted. Forgot the loop for 'b' in the final state. Please consider that. 1 votes 1 votes Ramij commented Dec 19, 2018 reply Follow Share Thanks,, got it. 0 votes 0 votes kumar.dilip commented Dec 19, 2018 reply Follow Share Utkarsh Joshi what about the string abbbbb or abbbb. 0 votes 0 votes Utkarsh Joshi commented Dec 19, 2018 reply Follow Share kumar.dilip read above comments 0 votes 0 votes shreyansh jain commented Dec 19, 2018 reply Follow Share @jatin khachane 1 nope, yours is not even accepting abb ! 0 votes 0 votes jatin khachane 1 commented Dec 19, 2018 reply Follow Share ohh .. have to edit in above diagram by utkarsh ..from final state transition for b is not shown 0 votes 0 votes Utkarsh Joshi commented Dec 19, 2018 reply Follow Share Forgot the loop for 'b' in the final state. Please consider that. PLEASE READ THIS COMMENT. 0 votes 0 votes altamash commented Dec 27, 2018 reply Follow Share 5 state = 4 for abb and 1 reject state if it start from b 0 votes 0 votes Shiva Sagar Rao commented Apr 28, 2021 reply Follow Share Duplicate: https://gateoverflow.in/278153/me-test-series-dfa-states 0 votes 0 votes Hira Thakur commented Dec 1, 2021 reply Follow Share Utkarsh Joshi your DFA is invalid for strings like $abbaabb,abbaabbb,abbbab$. for the final state on input, $b$ self-loop is there. 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes answer is 6 , edit: yeah the smallest string is abb rballiwal answered Dec 14, 2018 rballiwal comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes RE = abb + abb(a+b) *b Draw a DFA for above Regular Expression (key point is : smallest string will be 'abb') Devwritt answered Dec 19, 2018 Devwritt comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 5 state is required abhishekmehta4u answered Mar 30, 2019 abhishekmehta4u comment Share Follow See 1 comment See all 1 1 comment reply rishu1812 commented Apr 15, 2020 reply Follow Share your dfa is excepting abab, which do not start with abb. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes 6 states required as ab2 requires 4 states and b requires one state and one dead state 2021 answered Dec 1, 2021 2021 comment Share Follow See all 0 reply Please log in or register to add a comment.