Design FSA accepting even number of a's

Idea

We only need to remember whether the number of a's read so far is even or odd. So two states are enough: q0 (even number of a's, including zero) and q1 (odd number). Reading a toggles the state; reading b does not change it.

Formal definition

M = (Q, Σ, δ, q0, F) where

• Q = {q0, q1}
• Σ = {a, b}
• Start state q0
• F = {q0} (final state, since the empty string has zero a's, which is even)
• δ is given by the table below.

Transition table

(→ start state, * final state)

Transition diagram

          b                      b
         ┌─┐                    ┌─┐
         ↓ │                    ↓ │
  ──→ (( q0 )) ───────a──────→ ( q1 )
            ↑                     │
            └──────────a──────────┘

Trace

• "abab": q0 –a→ q1 –b→ q1 –a→ q0 –b→ q0. Ends in q0, accepted (2 a's).
• "baab": q0 –b→ q0 –a→ q1 –a→ q0 –b→ q0, accepted.
• "ab": q0 –a→ q1 –b→ q1, rejected (1 a).

The language is L = {w ∈ {a, b}* : number of a's in w is even} = b*(abab)*. I verified the machine against the count of a's for all strings up to length 8.