DFA — Deterministic Finite Automaton

A Deterministic Finite Automaton (DFA) is the simplest model of computation. Despite its simplicity, it's the mathematical foundation of every regex engine in existence.

Formal definition — a DFA is a 5-tuple (Q, Σ, δ, q0, F):
- Q — finite set of states
- Σ (sigma) — input alphabet (set of allowed symbols, e.g. {0,1} or {a-z})
- δ (delta) — transition function: δ(state, symbol) → next_state. DETERMINISTIC: exactly one next state for every (state, symbol) pair
- q0 — start state (q0 ∈ Q)
- F — set of accept states (F ⊆ Q)

How a DFA processes input:
① Start in state q0
② Read input symbols one by one, left to right
③ For each symbol, follow the transition δ(current_state, symbol) → new_state
④ After reading all input: if current state ∈ F → ACCEPT, else → REJECT

The DFA has NO memory beyond its current state. No stack, no tape. Just which state it's in. This is its fundamental limitation — it cannot count.

What DFAs CAN recognize (Regular Languages):
- Strings ending in "ab": build states tracking last two chars seen
- Strings with even number of 0s: two states (even/odd), toggle on each 0
- Valid binary numbers divisible by 3: 3 states (remainder 0, 1, 2)
- Email-like patterns, identifiers, keywords in programming languages

What DFAs CANNOT recognize:
- aⁿbⁿ (n a's followed by n b's) — needs to COUNT, DFA can't
- Palindromes — needs to remember the whole first half
- Balanced parentheses — needs unbounded counting
These require a stack (Pushdown Automaton) or more.

Dead state: if there's no valid transition for a (state, symbol) pair, the DFA goes to a dead/trap state (non-accepting) and stays there. All remaining input is consumed and the string is rejected.

Extended transition function δ*: δ*(q, ε) = q (empty string keeps you in same state). δ*(q, wa) = δ(δ*(q, w), a). This formally defines what happens on a full string.

The Pumping Lemma for Regular Languages: if L is regular, then strings long enough can be "pumped" (repeated middle section) and still be in L. Used to PROVE a language is NOT regular — find a string where pumping breaks membership. This is how we prove aⁿbⁿ is not regular.

1# Full DFA implementation
2
3class DFA:
4    def __init__(self, states, alphabet, transitions, start, accept):
5        """
6        transitions: dict of {(state, symbol): next_state}
7        """
8        self.states      = states
9        self.alphabet    = alphabet
10        self.transitions = transitions
11        self.start       = start
12        self.accept      = accept
13
14    def run(self, input_string, verbose=False):
15        current = self.start
16        if verbose:
17            print(f"  Start: {current}")
18        for symbol in input_string:
19            if symbol not in self.alphabet:
20                raise ValueError(f"Symbol '{symbol}' not in alphabet {self.alphabet}")
21            key = (current, symbol)
22            current = self.transitions.get(key, "DEAD")
23            if verbose:
24                print(f"  read '{symbol}' → {current}")
25        result = current in self.accept
26        if verbose:
27            print(f"  Final: {current} → {'ACCEPT ✓' if result else 'REJECT ✗'}")
28        return result
29
30    def accepts(self, string):
31        return self.run(string)
32
33
34# ── DFA 1: strings containing "ab" ────────────────────
35dfa_ab = DFA(
36    states     = {"q0", "q1", "q2"},
37    alphabet   = {"a", "b"},
38    transitions = {
39        ("q0","a"): "q1", ("q0","b"): "q0",
40        ("q1","a"): "q1", ("q1","b"): "q2",
41        ("q2","a"): "q2", ("q2","b"): "q2",
42    },
43    start  = "q0",
44    accept = {"q2"},
45)
46
47print("DFA: strings containing 'ab'")
48tests = ["ab", "aab", "bab", "ba", "bba", "ababab", "", "b", "aaa"]
49for s in tests:
50    result = dfa_ab.accepts(s)
51    print(f"  '{s}' → {'ACCEPT ✓' if result else 'REJECT ✗'}")
52
53# ── DFA 2: even number of 0s ──────────────────────────
54dfa_even0 = DFA(
55    states     = {"even", "odd"},
56    alphabet   = {"0", "1"},
57    transitions = {
58        ("even","0"): "odd",  ("even","1"): "even",
59        ("odd", "0"): "even", ("odd", "1"): "odd",
60    },
61    start  = "even",
62    accept = {"even"},
63)
64
65print("
66DFA: even number of 0s")
67for s in ["", "1", "0", "00", "010", "0110", "001", "10100"]:
68    count = s.count("0")
69    result = dfa_even0.accepts(s)
70    print(f"  '{s}' (zeros={count}) → {'ACCEPT ✓' if result else 'REJECT ✗'}")
71
72# ── DFA 3: binary numbers divisible by 3 ──────────────
73# States = remainder (0, 1, 2)
74# Reading bit b: new_remainder = (2*remainder + b) % 3
75dfa_div3 = DFA(
76    states     = {"r0", "r1", "r2"},
77    alphabet   = {"0", "1"},
78    transitions = {
79        ("r0","0"): "r0", ("r0","1"): "r1",
80        ("r1","0"): "r2", ("r1","1"): "r0",
81        ("r2","0"): "r1", ("r2","1"): "r2",
82    },
83    start  = "r0",
84    accept = {"r0"},
85)
86
87print("
88DFA: binary numbers divisible by 3")
89for n in [0, 3, 6, 9, 1, 2, 4, 7]:
90    binary = bin(n)[2:]
91    result = dfa_div3.accepts(binary)
92    expected = n % 3 == 0
93    check = "✓" if result == expected else "✗ BUG"
94    print(f"  {n:>3} = '{binary}' → {'ACCEPT' if result else 'REJECT'} {check}")
95
96# ── Pumping Lemma demo: prove a^n b^n is not regular ──
97print("
98Pumping Lemma — why a^n b^n is NOT regular:")
99print("  Assume it IS regular with pumping length p")
100print("  Choose s = a^p b^p  (length 2p ≥ p)")
101print("  Any split s=xyz where |xy|≤p means y = a^k (k≥1)")
102print("  Pump: xy²z = a^(p+k) b^p  → more a's than b's")
103print("  This is NOT in the language → CONTRADICTION")
104print("  Therefore a^n b^n is NOT regular ∎")