Search code examples
computer-scienceregular-languagefinite-automata

Finite Automata


How to Design a DFA over the alphabet {0,1}: The set of all strings such that the number of 1's is even and the number of 0's is a multiple of 3.


Solution

  • Use modulo counters in your states like this:

    state q[k,l] stands for k is the number of 1s read mod 2, and l the number of 0s read mod 3.

    q[0,0] is the start state, q[1,2] is the unique accepting state. There are six states overall, the transitions should be obvious.