Need to construct DFA (deterministic finite automaton)

Question

I need to construct a DFA which recognises all the strings made solely from 0s and 1s, so that thay have an even number of zeros and number of ones divisible by 3. I found an automaton for the case of even number of 0s and even number of 1s:

I tried going from here by adding some states, changing branches, etc.. However I remained unsuccessful usually losing track of what's the automaton doing beacuse of branches and states I'd add. Any help would be greatly appreciated.

Answer 1

You need states which record the divisibility by 2 and by 3, which means you need 6 states. Just call them 0|0, 1|0, 0|1, 1|1, 0|2, 1|2. The first digit tells you that when you reach the state, you have an even or odd number of zeros, the 2nd digit tells you that when you reach the state, you have a number of 1s that, when divided by 3, give the given modulus.

Your state diagram contains:

0|x   --0-->   1|x
1|x   --0-->   0|x 
y|0   --1-->   y|1
y|1   --1-->   y|2
y|2   --1-->   y|0

The start state is 0|0, which is also the only stop state.

The important bit to understand is that each state records the the modulus of the number of zeros or ones read when divided by 2, respectively 3. The 0|0 is then modulus 0 in both cases, which is the accepting criteria. This all works, because the number of different states to keep track of is finite. The name DFA tells us already that it would not work for an infinite number of states to track.