1 1 vote Consider the set of all binary strings where the difference between the number of 0’s and number of 1’s is even. The minimum number of states in a DFA that accepts the given set is _____________? (kindly explain the approach to this problem) Theory of Computation minimal-state-automata finite-automata theory-of-computation number-of-states + – stillhere 1.1k views answer comment Share Follow Print See 1 comment 1 1 comment reply none30 commented Sep 10, 2023 reply Follow flag The minimum number of states in DFA will be 4. 0 0 replyShare Please log in or register to add a comment.
Best answer 2 2 votes Given the difference between no of 0s and 1s is even which is possible only when both the no of 1s and 0s are even or both are odd. by this we will get 4 states but we can apply partition algorithm to get min 2 state dfa. AGNIDEB MUKHERJEE answered Sep 10, 2023 • selected Nov 20, 2023 by stillhere AGNIDEB MUKHERJEE comment Share Follow See all 3 Comments 3 3 Comments reply stillhere commented Sep 10, 2023 reply Follow flag Thank you, didn’t knew about “partition algorithm”, gonna learn it right now. 1 1 replyShare mili_dhara commented Nov 14, 2023 reply Follow flag Will you please draw the DFA? 0 0 replyShare AGNIDEB MUKHERJEE commented Nov 14, 2023 reply Follow flag i am not able to upload the image see you can do like this.Consider 2 states(A,B) (A-final st) δ(A,0)=δ(A,1)=B δ(B,0)=δ(B,1)=A 0 0 replyShare Please log in or register to add a comment.
