3 votes 3 votes What are the Number of states in minimum DFA that accepts Binary strings when interpreted as decimal mod 12 give 0 as remainder.Also give DFA. Theory of Computation minimal-state-automata theory-of-computation + – Himanshu1 asked Nov 2, 2015 Himanshu1 1.4k views answer comment Share Follow See 1 comment See all 1 1 comment reply minal commented Nov 4, 2015 reply Follow Share http://stackoverflow.com/questions/21897554/design-dfa-accepting-binary-strings-divisible-by-a-number-n it may help you 2 votes 2 votes Please log in or register to add a comment.
Best answer 3 votes 3 votes I m getting 5 states 0 1 -> q0 (F) q0 q1 q1 q2 q3 q2 q1 q2 q3 q4 q1 q4 q0 q1 Himanshu1 answered Nov 6, 2015 selected Nov 26, 2015 by Himanshu1 Himanshu1 comment Share Follow See all 3 Comments See all 3 3 Comments reply shekhar chauhan commented Apr 20, 2016 reply Follow Share Why did you use only 5 states here ? Can you be more clear about this explanation .? 1 votes 1 votes Himanshu1 commented Apr 21, 2016 reply Follow Share A number is divisible by 12 , if it is divisble by 3 as well as divisible by 4. Make 2 dfas for : 1) divisibility by 3 2) divisibility by 4 : For divisibility by 4 , a binary number must end with '00'. >> you can try to make product automaton & then minimize it. 1 votes 1 votes Bikram commented Aug 25, 2017 reply Follow Share Detail explanation about how to draw Transition table for this kind of questions : Click me 2 votes 2 votes Please log in or register to add a comment.
0 votes 0 votes state 0 1 >>q0(Final) q0 q1 q1 q2 q3 q2 q1 q2 q3 q4 q1 q4 q0 q1 Corrected now...Thanks to Amsar Sokt abby murali answered Nov 6, 2015 edited Nov 7, 2015 by abby murali abby murali comment Share Follow See 1 comment See all 1 1 comment reply Himanshu1 commented Nov 6, 2015 reply Follow Share I m getting 5 states 0 1 -> q0 (F) q0 q1 q1 q2 q3 q2 q1 q2 q3 q4 q1 q4 q0 q1 you do check.. 1 votes 1 votes Please log in or register to add a comment.