6 votes 6 votes How many states are there in a minimum state deterministic finite automaton accepting the language $L = \{w \mid w \in \{0,1\}^*,$ number of 0's is divisible by 2 and number of 1's is divisible by 5, respectively $\}$? 7 9 10 11 Theory of Computation theory-of-computation isro2014 minimal-state-automata + – kvkumar asked Jun 29, 2016 kvkumar 5.3k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 11 votes 11 votes Number of states=10 Hence,Option(C)10 is the correct choice. LeenSharma answered Jun 30, 2016 • selected Jul 1, 2016 by kvkumar LeenSharma comment Share Follow See all 0 reply Please log in or register to add a comment.
10 votes 10 votes ANSWER: OPTION C In General If number of 0's is divisible by 'm' and number of 1's is divisible by 'n' , then no. of states = m*n so here Answer is = 2*5 =10 Devwritt answered Jun 30, 2016 Devwritt comment Share Follow See all 2 Comments See all 2 2 Comments reply vandana commented Jul 2, 2016 reply Follow Share nice explanation 0 votes 0 votes Devwritt commented Jul 2, 2016 reply Follow Share Thank you! 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes no of states in mfa is 10 kvkumar answered Jun 29, 2016 kvkumar comment Share Follow See all 0 reply Please log in or register to add a comment.
3 votes 3 votes Answer will be 10 states. 2 * 5 = 10. This is a direct consequence of Myhill-Nerode theorem. http://courses.cs.washington.edu/courses/cse322/05wi/handouts/MyhillNerode.pdf Regina Phalange answered Mar 22, 2017 Regina Phalange comment Share Follow See all 0 reply Please log in or register to add a comment.