Skip to main content

DFA: even a and odd b

Short answer

Use four states representing (a-count mod2, b-count mod2): q00 (even, even) start, q01 (even, odd) final, q10 (odd, even), q11 (odd, odd). On a, toggle first component; on b, toggle second. Accepts when state is q01.

Construct a DFA over {a, b} accepting strings having an even number of a's and an odd number of b's.

Idea. Remember only the parity of the number of a's and the parity of the number of b's. This gives 4 states: qᵢⱼ means (a-count mod 2 = i, b-count mod 2 = j).

M = (Q, {a, b}, δ, q00, {q01}) with Q = {q00, q01, q10, q11}.

Transition table

Stateab
→ q00q10q01
*q01q11q00
q10q00q11
q11q01q10

Reading a flips the first index, reading b flips the second. The final state is q01 (even a's, odd b's).

Diagram

           a                  a
  ──►(q00) <──────────> (q10)
      ▲                    ▲
    b │                    │ b
      ▼                    ▼
    ((q01)) <──────────> (q11)
           a                  a

Every edge is two-way: a joins q00–q10 and q01–q11; b joins q00–q01 and q10–q11. Double circle = final state.

Test

  • "aab": q00 →a q10 →a q00 →b q01, final, accepted (2 a's, 1 b).
  • "ab": q00 → q10 → q11, not final, rejected (1 a).
  • "b": q00 → q01, accepted.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Theory of Computation chapter 2 questions →