Deterministic Finite Automata (DFA) — Design, Transition Tables and a Python Simulator

A Deterministic Finite Automaton (DFA) is the simplest computer: it reads a string one symbol at a time, moves between a fixed number of states, and at the end says yes or no. No extra memory — just "which state am I in?". Despite that, DFAs power regex engines, lexers, vending machines and protocol checkers.

1. Definition: the 5-tuple

A DFA M = (Q, Σ, δ, q₀, F):

A string is accepted if, after reading all of it, the DFA is in a state in F.

2. Example: binary strings ending in 01

States remember "how much of the pattern 01 have I just seen at the end?":

• q0 — nothing useful
• q1 — last symbol was 0
• q2 — last two symbols were 01 (accepting)

Transition table (→ start, * accepting):

3. A reusable DFA simulator

class DFA:
    def __init__(self, delta, start, accepting):
        self.delta, self.start, self.accepting = delta, start, accepting

    def run(self, w, trace=False):
        state = self.start
        path = [state]
        for ch in w:
            state = self.delta[(state, ch)]
            path.append(state)
        if trace:
            print(f"{w:>8}: {' -> '.join(path)}  {'ACCEPT' if state in self.accepting else 'reject'}")
        return state in self.accepting

ends_01 = DFA({("q0", "0"): "q1", ("q0", "1"): "q0",
               ("q1", "0"): "q1", ("q1", "1"): "q2",
               ("q2", "0"): "q1", ("q2", "1"): "q0"}, "q0", {"q2"})

for w in ["1101", "0110", "01", "1001"]:
    ends_01.run(w, trace=True)

# verify against the definition on every string up to length 10
from itertools import product
ok = all(ends_01.run("".join(t)) == "".join(t).endswith("01")
         for n in range(11) for t in product("01", repeat=n))
print("matches 'ends with 01' on all 2047 strings up to length 10:", ok)

    1101: q0 -> q0 -> q0 -> q1 -> q2  ACCEPT
    0110: q0 -> q1 -> q2 -> q0 -> q1  reject
      01: q0 -> q1 -> q2  ACCEPT
    1001: q0 -> q0 -> q1 -> q1 -> q2  ACCEPT
matches 'ends with 01' on all 2047 strings up to length 10: True

Checking a machine against a plain-Python definition on every short string is the fastest way to catch design mistakes — use it when practising.

4. Design patterns

"Contains substring w" — states track the longest prefix of w seen so far; the final state loops on everything.

"Number of a's is even" — two states: even/odd; flip on a, stay on b.

"Divisible by k" (binary) — states are remainders 0 … k−1. Reading bit b from remainder r gives new remainder (2r + b) mod k.

class DFA:                                   # same simulator as above, compact
    def __init__(self, delta, start, accepting):
        self.delta, self.start, self.accepting = delta, start, accepting
    def run(self, w):
        state = self.start
        for ch in w:
            state = self.delta[(state, ch)]
        return state in self.accepting

def divisible_by(k):
    delta = {(r, b): (2 * r + int(b)) % k for r in range(k) for b in "01"}
    return DFA(delta, 0, {0})

div3 = divisible_by(3)
tests = [bin(n)[2:] for n in [6, 7, 9, 10, 12, 21]]
print([(int(w, 2), div3.run(w)) for w in tests])
print("all n < 2000 correct:", all(div3.run(bin(n)[2:]) == (n % 3 == 0) for n in range(1, 2000)))

[(6, True), (7, False), (9, True), (10, False), (12, True), (21, True)]
all n < 2000 correct: True

Counting minimum states (exam favourite):

The dead (trap) state is a non-accepting state that loops to itself on everything — needed because a DFA must have a transition for every symbol.

5. Combining DFAs: product construction

To accept strings in L₁ and L₂, run both DFAs at once: states are pairs (p, q). Accept if both components accept (intersection) or either does (union). Complement: swap accepting and non-accepting states of a complete DFA.

class DFA:                                   # same simulator as above, compact
    def __init__(self, delta, start, accepting):
        self.delta, self.start, self.accepting = delta, start, accepting
    def run(self, w):
        state = self.start
        for ch in w:
            state = self.delta[(state, ch)]
        return state in self.accepting

ends_01 = DFA({("q0", "0"): "q1", ("q0", "1"): "q0", ("q1", "0"): "q1", ("q1", "1"): "q2",
               ("q2", "0"): "q1", ("q2", "1"): "q0"}, "q0", {"q2"})
div3 = DFA({(r, b): (2 * r + int(b)) % 3 for r in range(3) for b in "01"}, 0, {0})

def product_dfa(A, B, alphabet, mode="and"):
    delta, start = {}, (A.start, B.start)
    todo, seen = [start], {start}
    while todo:
        p, q = todo.pop()
        for c in alphabet:
            nxt = (A.delta[(p, c)], B.delta[(q, c)])
            delta[((p, q), c)] = nxt
            if nxt not in seen:
                seen.add(nxt); todo.append(nxt)
    if mode == "and":
        acc = {(p, q) for p, q in seen if p in A.accepting and q in B.accepting}
    else:
        acc = {(p, q) for p, q in seen if p in A.accepting or q in B.accepting}
    return DFA(delta, start, acc), len(seen)

both, n_states = product_dfa(ends_01, div3, "01")
print("states in product:", n_states)
print([(w, int(w, 2), both.run(w)) for w in ["1001", "101", "1101", "11001"]])

states in product: 9
[('1001', 9, True), ('101', 5, False), ('1101', 13, False), ('11001', 25, False)]

1001 (9) ends in 01 and is divisible by 3 → accepted; 101 (5) ends in 01 but isn't divisible by 3.

6. Real-world state machines

• Order status: placed → paid → shipped → delivered (no jumping from placed to delivered).
• Login lockout: 0, 1, 2 failures → locked.
• Lexers: recognising identifiers, numbers and keywords in a compiler.
• UI flows and games: menus, levels, character states.

Writing these as explicit state machines (a transition table, rejecting invalid transitions) prevents a whole class of bugs.

Common mistakes

• Missing transitions — a DFA needs one for every (state, symbol) pair; add a dead state.
• Making the start state accepting by accident (then ε is accepted).
• For "divisible by k", using r·10 instead of 2r (binary) — the base matters.
• Forgetting that complement only works on a complete DFA.

Quick recap

• DFA = (Q, Σ, δ, q₀, F); exactly one move per state and symbol; accept if the run ends in F.
• States = what you need to remember (pattern progress, counts mod k, remainders).
• Divisible by k: δ(r, b) = (2r + b) mod k.
• Product construction gives intersection/union; swapping final states gives complement.