C16: Automata, decidability, reductions, and complexity classes

A. Prerequisites and observable goals#

Level: Degree core introduction; formal theory requires further proof practice beyond this module.

B. The central question: which problems can a computational model solve?#

A language is a set of finite strings over an alphabet. A recognizer decides or attempts to recognize membership under a specified model. A deterministic finite automaton (DFA) has finitely many states, a start state, accepting states, and a transition for each state and alphabet symbol. Its state summarizes all information about the prefix that matters for future acceptance.

For strings over $\{a\}$ containing an even number of symbols, two states suffice: even and odd. Start in even, toggle on every $a$, and accept only even. The empty string is accepted because zero is even. An invariant proves correctness: after reading $k$ symbols, the state is even exactly when $k$ is even. Initialization holds at $k=0$, and each transition toggles parity.

The double circle means accepting, not “more important.” This finite machine remembers parity, not the exact count. A DFA cannot remember an unbounded integer in a fixed finite set of states.

C. Finite memory has limits#

Regular languages are exactly those recognized by finite automata and, under the classical definition, regular expressions. Some programming-library “regex” features, such as backreferences, go beyond classical regular expressions. Do not transfer a theorem about finite automata to every library feature sharing a name.

Consider $L=\{a^n b^n:n\ge0\}$. Suppose a DFA with $m$ states recognized it. Among the $m+1$ prefixes $a^0,a^1,\ldots,a^m$, two distinct lengths $i<j$ reach the same state by the pigeonhole principle. Appending $b^i$ makes the first string belong to $L$ and the second not belong. Starting from the same state and reading the same suffix cannot produce different acceptance decisions, a contradiction. Thus no DFA recognizes this language.

A context-free grammar can generate it using $S\to aSb\mid\epsilon$. A pushdown automaton adds a stack and can match unbounded nested structure. Balanced parentheses are a similar motivating example. “More expressive” does not mean “always better”: finite-state models can be easier to verify, serialize, and exhaustively explore for protocol control states.

D. Deciding differs from recognizing#

A decider halts on every input with a yes or no answer. A recognizer for a language must accept strings in the language, but may run forever on strings outside it. An algorithm that eventually finds a solution when one exists is not necessarily a decision procedure for whether a solution exists.

The halting problem asks whether an arbitrary program halts on an arbitrary input. Assume a total program $H(p,x)$ answers this correctly. Construct $D(p)$ to loop forever when $H(p,p)$ says “halts,” and halt when it says “does not halt.” Ask what $D(D)$ does. If $H(D,D)$ says halts, construction makes it loop; if it says does not halt, construction makes it halt. Both contradict correctness. Therefore no such total general halting decider exists for a computationally universal model.

This does not imply that no individual program’s termination can be proved. C02’s decreasing interval and C05’s induction prove termination for specific algorithms. Undecidability concerns a single algorithm that answers every instance of the general problem. It is not an excuse to stop analyzing a bounded program.

E. A reduction transfers a solution method in one direction#

A many-one reduction from decision problem $A$ to $B$ transforms an instance $x$ into $f(x)$ such that $x\in A$ exactly when $f(x)\in B$. Then a solver for $B$, combined with the transformation, solves $A$. To show $B$ is at least as hard as a known hard $A$, reduce $A$ to $B$, not the reverse. The transformation’s computational cost matters when discussing complexity classes.

P is the class of decision problems solvable in polynomial time by a deterministic algorithm under a standard discrete computational model. NP is the class with polynomial-size certificates verifiable in polynomial time, equivalently nondeterministic polynomial-time decidability. NP does not stand for “not polynomial.” Every problem in P is in NP: a verifier can simply decide the instance without needing a certificate.

A problem is NP-hard if every problem in NP reduces to it by the specified polynomial-time reduction. It is NP-complete if it is both NP-hard and in NP. NP-hard problems need not themselves be decision problems in NP; optimization problems are often called NP-hard through associated reductions. Boolean satisfiability is a foundational NP-complete decision problem. The P-versus-NP question remains unresolved in the authoritative problem statement checked for this edition; this book neither assumes $P=NP$ nor assumes a proof of $P\ne NP$. [PNP]

An exponential-looking implementation does not prove a problem requires exponential time. Conversely, a polynomial bound can still be impractical because of its degree, constants, or input representation. Distinguish worst-case classification, approximation guarantees, special-case structure, and measured performance.

F. Equivalence by exploring a product graph#

Two DFAs over the same alphabet are equivalent if they accept exactly the same strings. Form a product state $(u,v)$ recording both current states. Start at their start-state pair. A pair is distinguishing if exactly one component is accepting. Each symbol advances both machines. Breadth-first search finds a shortest word leading to a distinguishing pair, or exhausts all reachable pairs and proves equivalence under the supplied total transition tables.

There are at most $|Q_A||Q_B|$ product states. A graph implementation with parent links needs $O(|Q_A||Q_B||\Sigma|)$ transition work plus reconstruction. Our readable lab stores a word with each queued state, so copying strings can add overhead proportional to witness length; do not silently claim the optimal memory bound for this convenient representation. The algorithm’s finiteness, not an arbitrary maximum string length, establishes that exhaustion is meaningful.

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C16#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""C16.05: deterministic finite-state machines with total transitions."""
from collections import deque

def accepts(start, finals: set, delta: dict, alphabet: set, word: str) -> bool:
    state = start
    for symbol in word:
        if symbol not in alphabet:
            raise ValueError("symbol outside alphabet")
        state = delta[state, symbol]
    return state in finals

def distinguishing_word(a, b, alphabet: set[str]) -> str | None:
    """Each machine is (start, final_states, transition_dictionary)."""
    start = (a[0], b[0])
    todo = deque([(start, "")])
    seen = {start}
    while todo:
        (u, v), word = todo.popleft()
        if (u in a[1]) != (v in b[1]):
            return word
        for c in sorted(alphabet):
            pair = (a[2][u, c], b[2][v, c])
            if pair not in seen:
                seen.add(pair)
                todo.append((pair, word + c))
    return None

if __name__ == "__main__":
    even = (0, {0}, {(0, "a"): 1, (1, "a"): 0})
    all_words = (0, {0}, {(0, "a"): 0})
    print(repr(distinguishing_word(even, all_words, {"a"})))

I. Retention and readiness#

Retrieve the pigeonhole principle, BFS, and proof by contradiction. Advance when you can explain why a reduction’s arrow points toward the hypothetical solver and why finite-state equivalence is decidable while arbitrary program equivalence is much harder. Continue with a formal automata and computability course, then complexity and reductions with full proofs.