8 votes 8 votes Construct a minimal DFA which accepts set of all strings over {a,b} such that second symbol from RHS is 'a'. Theory of Computation finite-automata theory-of-computation + – Vivek Jain asked Aug 13, 2016 Vivek Jain 11.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 28 votes 28 votes 4 states are needed... papesh answered Aug 13, 2016 • selected Aug 16, 2016 by ManojK papesh comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments ahujabharat15 commented Mar 25, 2021 reply Follow Share I tried multiple cases on it, seems fine to me. 0 votes 0 votes Chandrabhan Vishwa 1 commented Aug 25, 2021 reply Follow Share @Marunmai it is not accept aaa 0 votes 0 votes Jakki commented Aug 25, 2023 reply Follow Share in this case "aaa" Is not accepted 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes This a complex type question if we directly try to create a dfa.The best method is create an nfa then convert it to dfa using subset construction method :(check video ) Kiran005 answered Jun 3, 2018 Kiran005 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Minimum number of states required construct DFA where Nth bit from last is fixed is, pow(2,n); in above example n = 2, so pow(2,2) = 4 states required Sac08 answered Dec 5, 2018 Sac08 comment Share Follow See all 2 Comments See all 2 2 Comments reply Akshay Pandey commented Jan 9, 2020 reply Follow Share There is better and universal formula to describe the number of states required to create a DFA. "If a minimal NFA contains N states then the minimal DFA for the same language will contain 2^N states.(In worst case)" 0 votes 0 votes darshansharma_ commented Apr 20, 2020 reply Follow Share It's proof? 0 votes 0 votes Please log in or register to add a comment.
