Deterministic FSM accepting a binary string whose number of zero is either multiple of 2, 3, or both

Question

I can build a FSM that accept binary string with multiple of 2 number of 0, and I can also build a FSM that accept binary string with multiple of 3 number of 0, but I cannot figure out how I can combine these 2 together and still stay deterministic. Any help? Thanks.

Answer 1

Imagine you could make a machine with an infinite row of states. Every time you see a zero, you transition to the next state in the row.

$$(0)\xrightarrow{0}(1)\xrightarrow{0}(2)\xrightarrow{0}(3)\xrightarrow{0}\ldots$$

Then the even numbered states should accept because they've seen an even number of zeros. And every third state should accept because they've seen a multiple of three states. The rest of the states shouldn't accept.

If you write out the pattern of accepting and non accepting states, you'll see that it looks like this:

AXAAAXAXAAAXA...

It forms a cycle with a period of 6=2*3 that repeats over and over again indefinitely.

It follows that you don't need an infinite number of states after all—a cycle of six will work.

---

If you didn't have this insight, you can always turn an NFA into a DFA as follows: If the NFA has states Q and starting state q0, then the DFA should have one state for every subset of Q. If the old machine would non deterministically transition into states q1, q2, or q3, the new machine just deterministically transitions to the state {q1,q2,q3}. The start state is the singleton q0, and the accepting states of the new machine are any subset containing an accepting state of the old machine.

There may be many more states in the new machine, but it will still be finite.