8 8 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 7.1k views answer comment Share Follow Print See all 4 Comments 4 4 Comments reply ritiksri8 commented Jul 31, 2024 reply Follow flag Deepak Poonia Sir,Is it ok to apply product automata here? 0 0 replyShare Satish_425 commented Sep 15, 2024 reply Follow flag Yes, even i made the product automata of both dfa where you will get total of 10 states. 0 0 replyShare ritiksri8 commented Sep 15, 2024 reply Follow flag The product automaton does not guarantee a minimum deterministic finite automaton (MDFA). For that, we need to show indistinguishable strings using the Myhill-Nerode theorem. The theorem helps identify equivalence classes of indistinguishable strings, which are used to minimize the DFA. 0 0 replyShare Satish_425 commented Sep 15, 2024 reply Follow flag yes, you are correct i did the same after product automata but after minimization number of states does not changed also i forgot to mention the use of " myhill-nerode theorem" in my previous comment . 0 0 replyShare Please log in or register to add a comment.
Best answer 13 13 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 0 reply Please log in or register to add a comment.
12 12 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 2 2 Comments reply vandana commented Jul 2, 2016 reply Follow flag nice explanation 0 0 replyShare Devwritt commented Jul 2, 2016 reply Follow flag Thank you! 0 0 replyShare Please log in or register to add a comment.
4 4 votes no of states in mfa is 10 kvkumar answered Jun 29, 2016 kvkumar comment Share Follow 0 reply Please log in or register to add a comment.
3 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 0 reply Please log in or register to add a comment.
