Skip to main content

DFA: even 0s and even 1s

Short answer

DFA with four states tracking parity mod 2 of 0's and 1's: q00 (even, even) start and accepting. Transitions: 0 flips first index, 1 flips second. 0110 returns to q00 (accepted); 010 ends in q01 (rejected).

Design a DFA for L = {x ∈ {0,1}* : x has an even number of 0's and an even number of 1's}.

Idea. Track the parity of 0's and 1's. Four states qᵢⱼ: i = number of 0's mod 2, j = number of 1's mod 2. The start state q00 is also the only final state (even, even; ε is accepted).

M = ({q00, q01, q10, q11}, {0, 1}, δ, q00, {q00})

State01
→ *q00q10q01
q01q11q00
q10q00q11
q11q01q10
          0                  0
  ──►((q00)) <──────────> (q10)
       ▲                    ▲
     1 │                    │ 1
       ▼                    ▼
      (q01) <──────────> (q11)
          0                  0

Each edge is two-way: 0 joins q00–q10 and q01–q11; 1 joins q00–q01 and q10–q11.

Test

  • "0110": q00 →0 q10 →1 q11 →1 q10 →0 q00. Accepted.
  • "010": q00 → q10 → q11 → q01. Rejected (two 0's, one 1).

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →