1 votes 1 votes 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 asked Sep 10, 2023 stillhere 482 views answer comment Share Follow See 1 comment See all 1 1 comment reply none30 commented Sep 10, 2023 reply Follow Share The minimum number of states in DFA will be 4. 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 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 See all 3 3 Comments reply stillhere commented Sep 10, 2023 reply Follow Share Thank you, didn’t knew about “partition algorithm”, gonna learn it right now. 1 votes 1 votes mili_dhara commented Nov 14, 2023 reply Follow Share Will you please draw the DFA? 0 votes 0 votes AGNIDEB MUKHERJEE commented Nov 14, 2023 reply Follow Share 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 votes 0 votes Please log in or register to add a comment.
