Minimal Finite Automata - Theory of Computation

Question

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)

Comments

The minimum number of states in DFA will be 4.

Answer 1

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.

Comments

Thank you, didn’t knew about “partition algorithm”, gonna learn it right now.

---

Will you please draw the DFA?

---

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