Finite Automata & Regular Languages

Before we can talk about machines, we need to talk about what those machines process.

An alphabet Σ is any finite, nonempty set of symbols. Examples: Σ = {0, 1} (binary), Σ = {a, b, …, z} (lowercase English), Σ = {if, else, int, +, (, ), …} (tokens of a programming language).

A string (or word) over Σ is a finite sequence of symbols from Σ. The empty string is written ε (epsilon) and has length 0. The set of all strings over Σ is written Σ* ("Σ star"), which includes ε, all length-1 strings, all length-2 strings, and so on — it is countably infinite.

A language L over Σ is simply a subset of Σ*: L ⊆ Σ*. Languages can be finite (the set of keywords in Python) or infinite (all strings with equal numbers of 0s and 1s). The empty language ∅ contains no strings at all; the language {ε} contains exactly the empty string.

Why does this matter? Every computational question — "does this program halt?", "is this input valid JSON?", "does this string match the pattern?" — can be phrased as a membership question: does a given string belong to a given language? The entire theory of computation is the study of which languages can be recognized by which kinds of machines.

# Python: basic language operations
Sigma = {'0', '1'}

# All strings over Sigma up to length 3
from itertools import product
Sigma_star_3 = [''.join(s) for n in range(4) for s in product(Sigma, repeat=n)]
# ['', '0', '1', '00', '01', '10', '11', '000', ...]

# A language: strings over {0,1} that end in '1'
L = {s for s in Sigma_star_3 if s.endswith('1')}
# {'1', '01', '11', '001', '011', '101', '111'}

A Deterministic Finite Automaton is a mathematical machine with five components:

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

• Q is a finite set of states
• Σ is the input alphabet
• δ: Q × Σ → Q is the transition function — given current state and next symbol, return next state (total, deterministic)
• q₀ ∈ Q is the start state
• F ⊆ Q is the set of accept states (final states)

The machine processes a string one symbol at a time, following δ from state to state. After consuming all symbols, it accepts if it is in a state in F, and rejects otherwise.

Formal definition of acceptance: The DFA M accepts string w = w₁w₂…wₙ iff there exists a sequence of states r₀, r₁, …, rₙ such that:

1. r₀ = q₀
2. δ(rᵢ, wᵢ₊₁) = rᵢ₊₁ for each i
3. rₙ ∈ F

Example: Build a DFA over {0,1} that accepts exactly the strings containing an even number of 1s.

• Q = {even, odd}, q₀ = even, F = {even}
• δ(even, 0) = even, δ(even, 1) = odd
• δ(odd, 0) = odd, δ(odd, 1) = even

Trace on input "0110": even→even→odd→even→even. Final state even ∈ F. Accept. ✓

Key insight: every DFA state encodes a equivalence class of the computation history that matters for the future. The "even" and "odd" states encode exactly the parity of 1s seen so far — nothing else is needed to decide future inputs.

# Python DFA simulation
def make_even_ones_dfa():
    Q = {'even', 'odd'}
    Sigma = {'0', '1'}
    delta = {
        ('even', '0'): 'even',
        ('even', '1'): 'odd',
        ('odd',  '0'): 'odd',
        ('odd',  '1'): 'even',
    }
    q0 = 'even'
    F  = {'even'}
    return (Q, Sigma, delta, q0, F)

def dfa_accepts(M, w):
    (Q, Sigma, delta, q0, F) = M
    state = q0
    for c in w:
        state = delta[(state, c)]
    return state in F

M = make_even_ones_dfa()
print(dfa_accepts(M, '0110'))  # True  (two 1s → even)
print(dfa_accepts(M, '111'))   # False (three 1s → odd)

A Nondeterministic Finite Automaton relaxes two constraints of the DFA:

1. From a state on a symbol, there can be zero, one, or many next states (not exactly one).
2. There are ε-transitions: the machine can move to a new state without consuming any input.

M = (Q, Σ, δ, q₀, F) where δ: Q × (Σ ∪ {ε}) → P(Q) (the power set of Q, i.e., a set of possible next states).

The NFA accepts string w iff there exists at least one accepting path through the computation tree. Conceptually, the NFA "guesses" which branch to take at each nondeterministic step. Practically, we think of it as exploring all branches in parallel.

Why NFAs? They are exponentially easier to design for many patterns. Consider the language: "strings over {a,b} whose second-to-last symbol is 'a'". A DFA for this over {a,b} needs 4 states and careful bookkeeping. An NFA for it needs only 3 states:

• q₀: start, loop on a and b
• q₁: just read 'a' (nondeterministically guess this is the second-to-last symbol)
• q₂ (accept): read one more symbol

δ(q₀, a) = {q₀, q₁}, δ(q₀, b) = {q₀}, δ(q₁, a) = {q₂}, δ(q₁, b) = {q₂}

The nondeterminism says: "I might be at the second-to-last position now, or I might not — I will try both simultaneously."

ε-closure: Given a set of states S, ε-closure(S) is all states reachable from S by following only ε-transitions (including S itself). This is computed by a simple BFS/DFS.

# Python NFA simulation (via parallel state tracking)
from collections import defaultdict

def epsilon_closure(delta_eps, states):
    """BFS over ε-transitions from a set of states."""
    closure = set(states)
    stack = list(states)
    while stack:
        s = stack.pop()
        for t in delta_eps.get((s, ''), set()):
            if t not in closure:
                closure.add(t)
                stack.append(t)
    return frozenset(closure)

def nfa_accepts(Q, delta, q0, F, w):
    """delta: dict (state, symbol|'') -> set of states"""
    current = epsilon_closure(delta, {q0})
    for c in w:
        next_states = set()
        for s in current:
            next_states |= delta.get((s, c), set())
        current = epsilon_closure(delta, next_states)
    return bool(current & F)  # any accepting state reachable?

Here is one of the great constructive proofs in all of CS: every NFA has an equivalent DFA. The language recognized is identical; we just pay a potentially exponential price in states.

The key insight: at any point in an NFA computation, you are in some set of NFA states simultaneously (because of nondeterminism). So make each set of NFA states a single DFA state. This is the subset construction (also called the powerset construction).

Algorithm: Given NFA N = (Q, Σ, δ_N, q₀, F_N), construct DFA M = (Q', Σ, δ_M, q₀', F') as follows:

• Q' = P(Q) — states of M are subsets of NFA states (only reachable ones need be computed)
• q₀' = ε-closure({q₀})
• For each DFA state R ∈ Q' and symbol a ∈ Σ:
  • δ_M(R, a) = ε-closure( ∪_{r ∈ R} δ_N(r, a) )
• F' = {R ∈ Q' | R ∩ F_N ≠ ∅} — DFA state is accepting iff it contains any NFA accepting state

Complexity: An NFA with n states can yield a DFA with up to 2ⁿ states. This is not just a theoretical bound — it is tight. There are explicit NFA families (e.g., "nth-to-last symbol is 'a'") where the minimal DFA provably requires 2ⁿ states.

Why the construction is correct: Formal proof is by induction on the length of input w. The invariant: after reading w, the DFA is in state ε-closure(NFA's possible states after w). Base case: both start at ε-closure({q₀}). Inductive step: reading one more symbol a from DFA state R gives ε-closure(∪_{r∈R} δ_N(r,a)), which is exactly the set of NFA states reachable on w·a.

Practical significance: Regex engines that compile to DFAs use exactly this construction. The grep and awk tools do this automatically — that is why they run in O(n) time on the input regardless of regex complexity, while backtracking regex engines can be exponentially slow.

def nfa_to_dfa(nfa_states, sigma, nfa_delta, nfa_q0, nfa_F):
    """Subset construction. Returns (dfa_delta, dfa_q0, dfa_F) as dicts/sets."""
    def eps_closure(states):
        closure = set(states)
        stack = list(states)
        while stack:
            s = stack.pop()
            for t in nfa_delta.get((s, ''), set()):
                if t not in closure:
                    closure.add(t); stack.append(t)
        return frozenset(closure)

    start = eps_closure({nfa_q0})
    dfa_delta = {}
    dfa_F = set()
    queue = [start]
    visited = {start}

    while queue:
        R = queue.pop(0)         # current DFA state (a frozenset)
        if R & nfa_F:            # if any NFA accept state in R
            dfa_F.add(R)
        for a in sigma:
            move = set()
            for r in R:
                move |= nfa_delta.get((r, a), set())
            S = eps_closure(move)
            dfa_delta[(R, a)] = S
            if S not in visited:
                visited.add(S); queue.append(S)

    return dfa_delta, start, dfa_F

The regular languages over Σ are exactly the languages recognized by DFAs (equivalently, NFAs). They are also exactly the languages describable by regular expressions. This triple equivalence (DFA = NFA = RegEx) is the fundamental theorem of regular languages.

Regular expressions (the formal, mathematical kind — not the PCRE extensions with backreferences) are defined inductively:

• Base cases: ∅ (empty language), ε (language {ε}), and 'a' for any a ∈ Σ (language {a}) are regular expressions.
• Inductive cases: if R and S are regular expressions, so are:
  • R ∪ S (union / alternation)
  • R ∘ S (concatenation)
  • R* (Kleene star: zero or more repetitions)

Every regular expression describes a regular language, and every regular language has a regular expression — proven by showing the equivalence with NFAs via Thompson's construction.

Thompson's Construction (RegEx → NFA): Inductively builds a small NFA for each regex operator:

• For 'a': two states with an a-transition
• For R∪S: new start with ε-transitions to both NFAs
• For R∘S: ε-transition from R's accept to S's start
• For R*: new start/accept with ε-transitions creating the loop

This is the algorithm inside every regex library that does not use backtracking (e.g., RE2, Go's regexp package, Rust's regex crate).

Important caveat: The "regular expressions" in Python's re module, PCRE, and most programming languages include backreferences like \1, which can match non-regular languages and make matching NP-hard in the worst case. The formal definition above (without backreferences) is what we mean in theory.

# Kleene star example: (ab)* matches "", "ab", "abab", ...
import re
pattern = r'^(ab)*$'
for s in ['', 'ab', 'abab', 'ababab', 'a', 'aba', 'b']:
    print(f'{s!r:12} -> {bool(re.match(pattern, s))}')
# Output:
# ''           -> True
# 'ab'         -> True
# 'abab'       -> True
# 'ababab'     -> True
# 'a'          -> False
# 'aba'        -> False
# 'b'          -> False

One of the most useful facts about regular languages is that they are closed under many natural operations — meaning if you start with regular languages and apply these operations, you always get a regular language back. This lets you compose recognizers.

Closure under union: If L₁ and L₂ are regular, so is L₁ ∪ L₂. Proof: Build NFAs N₁ and N₂ for L₁ and L₂. Introduce a new start state q with ε-transitions to both N₁'s and N₂'s start states. The resulting NFA recognizes L₁ ∪ L₂.

Closure under concatenation: If L₁ and L₂ are regular, so is L₁ ∘ L₂ = {xy | x ∈ L₁, y ∈ L₂}. Proof: Add ε-transitions from every accept state of N₁ to the start state of N₂.

Closure under Kleene star: If L is regular, so is L* = {ε} ∪ L ∪ LL ∪ LLL ∪ … Proof: Add a new start/accept state with ε-transitions to/from N's start/accept.

Closure under complement: If L is regular over Σ, so is L̄ = Σ* \ L. Proof: Take the DFA for L (crucially, a DFA, not NFA — DFAs are total, so every state has transitions for every symbol). Swap accept and non-accept states. Every string now either reaches a previously accepting state (and is now rejected) or a previously non-accepting state (now accepted). This works because DFAs are deterministic — there is exactly one state reached on any input, with no "maybe" paths.

Closure under intersection: By De Morgan's law, L₁ ∩ L₂ = complement(complement(L₁) ∪ complement(L₂)). Regular, since we are composing three closed operations. Direct construction: The product construction — DFA states are pairs (p, q) ∈ Q₁ × Q₂. Accept iff both components are accepting. This gives a direct O(|Q₁||Q₂|) construction.

Closure under difference, reverse, homomorphism, inverse homomorphism all hold as well, making regular languages an extraordinarily robust algebraic structure.

# Product construction: intersection of two DFAs
def dfa_intersect(M1, M2):
    """M1, M2: (delta, q0, F) where delta: (state,char)->state"""
    (d1, s1, F1), (d2, s2, F2) = M1, M2
    # Product DFA: states are (q1, q2) pairs
    def delta_prod(state, c):
        q1, q2 = state
        return (d1[(q1, c)], d2[(q2, c)])
    start = (s1, s2)
    # Accept only if BOTH component states are accepting
    def is_accept(state):
        return state[0] in F1 and state[1] in F2
    return delta_prod, start, is_accept

# Example: L1 = even number of a's, L2 = even number of b's
# Intersection = even number of BOTH a's and b's

Not every language is regular. The Pumping Lemma is the main tool for proving a language is not regular.

Theorem (Pumping Lemma for Regular Languages): If L is a regular language, then there exists a pumping length p ≥ 1 such that for every string w ∈ L with |w| ≥ p, we can write w = xyz where:

1. |y| ≥ 1 (y is nonempty)
2. |xy| ≤ p (the split happens in the first p characters)
3. For all i ≥ 0, xyⁱz ∈ L (pumping y any number of times stays in L)

Why is this true? If M is a DFA with p states and |w| ≥ p, then by the Pigeonhole Principle, the DFA's state sequence r₀, r₁, …, r_{|w|} must repeat some state within the first p+1 steps. Say rⱼ = rₖ with j < k ≤ p. Then x = w[0..j], y = w[j..k], z = w[k..end]. Since the machine returns to state rⱼ = rₖ after reading y, we can pump y any number of times and still reach the same accepting state.

How to use it to prove non-regularity: Proof by contradiction. Assume L is regular, let p be its pumping length. Choose a specific string w ∈ L with |w| ≥ p. Show that for every possible split w = xyz satisfying conditions 1 and 2, there exists some i where xyⁱz ∉ L. Contradiction.

Classic example: L = {0ⁿ1ⁿ | n ≥ 0} is not regular. Let p be the pumping length. Choose w = 0ᵖ1ᵖ. For any split with |xy| ≤ p and |y| ≥ 1, y consists entirely of 0s. Pumping y twice gives 0^(p+|y|)1^p which has more 0s than 1s — not in L. Contradiction.

Important caveat: The pumping lemma is a necessary but not sufficient condition for regularity. Passing the pumping lemma does not prove regularity. To prove a language IS regular, exhibit a DFA or regular expression.

# The pumping lemma is a proof technique, not code.
# But here is a program that TESTS the pumping condition for a given language:

def test_pumping(language_fn, p, w):
    """
    Try all splits w = xyz with |xy| <= p, |y| >= 1.
    For each, check if pumping i=0,1,2,3 stays in language.
    Returns True if ALL splits pump successfully (consistent with regularity).
    """
    for split1 in range(len(w) + 1):       # |x| = split1
        for split2 in range(split1 + 1, min(p + 1, len(w) + 1)):  # |xy| = split2
            x, y, z = w[:split1], w[split1:split2], w[split2:]
            if not y:  # |y| >= 1 required
                continue
            for i in [0, 2, 3]:  # pump down and up
                pumped = x + y * i + z
                if not language_fn(pumped):
                    print(f'PUMP FAILED: x={x!r} y={y!r} z={z!r} i={i} -> {pumped!r}')
                    return False
    return True

# L = {0^n 1^n | n >= 0}
def L_0n1n(s):
    n = len(s) // 2
    return len(s) % 2 == 0 and s == '0' * n + '1' * n

p = 4
w = '0' * p + '1' * p
test_pumping(L_0n1n, p, w)  # Will find a failing split

For any regular language, there is a unique minimal DFA — the DFA with the fewest states that recognizes it. The Myhill-Nerode theorem characterizes exactly how many states are needed and proves that minimality is unique.

Myhill-Nerode Theorem: Let L ⊆ Σ*. Define the equivalence relation ≡_L on strings: x ≡_L y iff for all z ∈ Σ*, xz ∈ L ↔ yz ∈ L (x and y are indistinguishable by any suffix). Then:

1. L is regular if and only if ≡_L has finitely many equivalence classes.
2. The number of equivalence classes of ≡_L equals the number of states in the minimal DFA for L.

Intuition: Two strings x and y are equivalent if no future input can distinguish them. Each equivalence class corresponds to a minimal DFA state — the state you should be in after reading a string in that class. This gives a language-theoretic definition of DFA states that is independent of any particular automaton construction.

DFA minimization algorithm (Hopcroft's algorithm, O(n log n)):

1. Remove unreachable states.
2. Start with partition P = {F, Q\F} (accepting vs. non-accepting).
3. Repeatedly refine: two states p, q are in the same class only if for every a ∈ Σ, δ(p,a) and δ(q,a) are in the same class.
4. Repeat until stable. Merge states in the same class.

Why minimization matters: Compiled regex libraries minimize the DFA after the subset construction to keep it small. The minimal DFA is the canonical form — two regexes recognize the same language iff their minimal DFAs are isomorphic, which gives you a decision algorithm for regex equivalence.

def minimize_dfa(states, sigma, delta, q0, F):
    """Table-filling (marking) algorithm for DFA minimization."""
    states = list(states)
    n = len(states)
    idx = {s: i for i, s in enumerate(states)}
    # Mark pairs: distinguishable[i][j] = True if (states[i], states[j]) distinguishable
    dist = [[False]*n for _ in range(n)]

    # Base: (accept, non-accept) pairs are distinguishable
    for i in range(n):
        for j in range(i+1, n):
            if (states[i] in F) != (states[j] in F):
                dist[i][j] = dist[j][i] = True

    # Propagate: if delta(p,a) and delta(q,a) are distinguishable, so are p and q
    changed = True
    while changed:
        changed = False
        for i in range(n):
            for j in range(i+1, n):
                if not dist[i][j]:
                    for a in sigma:
                        di = idx[delta[(states[i], a)]]
                        dj = idx[delta[(states[j], a)]]
                        if dist[di][dj]:
                            dist[i][j] = dist[j][i] = True
                            changed = True
                            break

    # Merge indistinguishable states (same equivalence class)
    merged = {states[i]: states[i] for i in range(n)}
    for i in range(n):
        for j in range(i+1, n):
            if not dist[i][j]:
                merged[states[j]] = merged[states[i]]  # union-find would be cleaner
    return merged  # map: old state -> representative of its equivalence class