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

Source: https://skills101.in/learn/theory-of-computation/dfa-deterministic-finite-automata — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-09.

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):

| Part | Meaning |
|---|---|
| **Q** | finite set of states |
| **Σ** | input alphabet |
| **δ: Q × Σ → Q** | transition function — **exactly one** next state for every state and symbol |
| **q₀** | start state |
| **F ⊆ Q** | accepting (final) states |

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)

![DFA for binary strings ending in 01: from q0 a 0 goes to q1 and a 1 stays in q0; from q1 a 0 stays in q1 and a 1 goes to the accepting state q2; from q2 a 0 goes to q1 and a 1 goes to q0](https://skills101.in/learn-img/theory-of-computation/dfa-ends-01.svg)

Transition table (→ start, * accepting):

| State | 0 | 1 |
|---|---|---|
| → q0 | q1 | q0 |
| q1 | q1 | q2 |
| * q2 | q1 | q0 |

## 3. A reusable DFA simulator

```python
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)
```

```text
    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**.

![DFA for binary numbers divisible by 3: three states for remainders 0, 1 and 2; reading a bit b from remainder r moves to remainder (2r + b) mod 3; remainder 0 is both the start and the accepting state](https://skills101.in/learn-img/theory-of-computation/dfa-div3.svg)

```python
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)))
```

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

**Counting minimum states** (exam favourite):

| Language over {0,1} | Minimum DFA states |
|---|---|
| strings ending in `01` | 3 |
| length divisible by k | k |
| binary number divisible by k (k odd) | k |
| strings with exactly 2 ones | 4 (0, 1, 2 ones, "too many" trap) |
| strings starting with `01` | 4 (start, saw 0, accept, trap) |

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.

```python
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"]])
```

```text
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.


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/dfa-deterministic-finite-automata