Computability and Formal Languages

Last updated: August 2026

Disclaimer: These are my personal notes compiled for my own reference and learning. They may contain errors, incomplete information, or personal interpretations. While I strive for accuracy, these notes are not peer-reviewed and should not be considered authoritative sources. Please consult official textbooks, research papers, or other reliable sources for academic or professional purposes.

Contents

  1. Finite automata and regular languages
  2. The Pumping Lemma and Myhill-Nerode
  3. Context-free languages and the Chomsky hierarchy, briefly
  4. Turing machines and decidability
  5. The Halting Problem is undecidable
  6. Reductions and Rice's theorem
  7. P, NP, and polynomial-time reductions
  8. Computation
  9. Common pitfalls
  10. Connections
  11. References

1. Finite automata and regular languages

Definition

A deterministic finite automaton (DFA) is $M=(Q,\Sigma,\delta,q_0,F)$: a finite set of states $Q$, alphabet $\Sigma$, transition function $\delta:Q\times\Sigma\to Q$, start state $q_0$, and accepting states $F\subseteq Q$. Extend $\delta$ to strings by $\hat\delta(q,\epsilon)=q$, $\hat\delta(q,wa)=\delta(\hat\delta(q,w),a)$. $M$ recognizes $L(M)=\{w\in\Sigma^*:\hat\delta(q_0,w)\in F\}$; $L$ is regular if some DFA recognizes it.

A DFA is the simplest possible model of computation with a reason to care about it mathematically: it has no memory beyond which of finitely many states it currently occupies. Everything in Section 2 is a consequence of that single restriction, made precise.

2. The Pumping Lemma and Myhill-Nerode

Theorem (Pumping Lemma)

If $L$ is regular, there is $p\geq1$ such that every $s\in L$ with $|s|\geq p$ can be written $s=xyz$ with $|xy|\leq p$, $|y|\geq1$, and $xy^iz\in L$ for every $i\geq0$.

Proof. Let $M$ be a DFA for $L$ with $p=|Q|$ states. For $s\in L$ with $|s|\geq p$, let $q_0,q_1,\ldots,q_p$ be the states $M$ visits reading the first $p$ characters of $s$ — that is $p+1$ states drawn from a set of only $p$, so by the pigeonhole principle $q_i=q_j$ for some $0\leq i<j\leq p$. Set $x=$ the length-$i$ prefix, $y=$ the substring from position $i$ to $j$ (so $|y|=j-i\geq1$), $z=$ the rest of $s$. Since reading $y$ takes $M$ from $q_i$ back to $q_i$, it can be read any number of times $i\geq0$ (including zero) without changing whether the rest of the computation accepts — so $xy^iz\in L$ for every $i\geq0$; and $|xy|=j\leq p$. ∎
Application — $\{0^n1^n:n\geq0\}$ is not regular

Suppose it were, with pumping length $p$. Take $s=0^p1^p$. Any decomposition $s=xyz$ with $|xy|\leq p$ has $xy$ entirely within the $0$-block, so $y=0^k$, $k\geq1$. Pumping down ($i=0$): $xz=0^{p-k}1^p$ has fewer $0$s than $1$s, so $xz\notin L$ — contradicting the lemma, which requires $xy^0z\in L$ for every valid decomposition. So no such $p$ exists, and $L$ is not regular.

Definition and Theorem (Myhill-Nerode)

Say $x\sim_Ly$ if for every $z$: $xz\in L\iff yz\in L$. If $L$ is regular, $\sim_L$ has finitely many equivalence classes (at most $|Q|$ for any recognizing DFA).

Proof. Given a DFA $M=(Q,\Sigma,\delta,q_0,F)$ for $L$, define $x\sim_My$ iff $\hat\delta(q_0,x)=\hat\delta(q_0,y)$ — at most $|Q|$ classes, trivially. If $x\sim_My$, then for every $z$, $\hat\delta(q_0,xz)=\hat\delta(\hat\delta(q_0,x),z)=\hat\delta(\hat\delta(q_0,y),z)=\hat\delta(q_0,yz)$, so $xz\in L\iff yz\in L$ — i.e. $x\sim_My\Rightarrow x\sim_Ly$. Since $\sim_M$ refines $\sim_L$, $\sim_L$ has at most as many classes as $\sim_M$, hence at most $|Q|$. ∎
Application, again — a second, independent proof

For $i\neq j$ (say $i<j$), take $z=1^i$: $0^iz=0^i1^i\in L$ but $0^jz=0^j1^i\notin L$ (unequal exponents). So $0^i\not\sim_L0^j$ for all $i\neq j$ — infinitely many pairwise-distinct equivalence classes, so by the theorem's contrapositive, $\{0^n1^n\}$ is not regular. This reaches the same conclusion as the Pumping Lemma by an entirely different route, and it generalizes further: Myhill-Nerode classes are exactly the minimal DFA's states, giving not just non-regularity but an exact minimum state count for any regular approximation (Figure 1).

Plot of the minimal number of DFA states needed to exactly recognize the truncated language 0 to the n, 1 to the n for n up to N, growing exactly as 2N+2, computed via Myhill-Nerode residual languages for N from 0 to 20.
Figure — Myhill-Nerode, computed exactly, for $\{0^n1^n:n\leq N\}$. Truncating the language to strings with $n\leq N$ makes it finite, hence trivially regular — but the minimal DFA needed grows linearly, exactly $2N+2$ states (computed directly from the Myhill-Nerode residual languages of each reachable prefix, not merely asserted). No single finite automaton can serve every truncation simultaneously, which is the concrete content behind the untruncated language failing to be regular at all.

3. Context-free languages and the Chomsky hierarchy, briefly

Regular languages sit at the bottom of a strict containment hierarchy; each level is generated by grammars with progressively fewer restrictions on production rules, and recognized by progressively more powerful machines.

The Chomsky hierarchy

Regular (right-linear grammars; DFA/NFA) $\subsetneq$ context-free (rules $A\to\gamma$, any $\gamma$; pushdown automata — a DFA plus a stack) $\subsetneq$ context-sensitive (rules $\alpha A\beta\to\alpha\gamma\beta$, $|\gamma|\geq1$; linear-bounded automata) $\subsetneq$ recursively enumerable (unrestricted grammars; Turing machines, Section 4).

$\{0^n1^n:n\geq0\}$, not regular (Section 2), is context-free: the grammar $S\to0S1\mid\epsilon$ generates exactly it, and a pushdown automaton recognizes it by pushing a marker per $0$ and popping one per $1$ — the single unbounded counter a stack provides is exactly the extra power a DFA's fixed state set lacks. Context-free languages have their own pumping lemma (with two pumped pieces instead of one, reflecting the stack's LIFO structure), not reproduced here; $\{a^nb^nc^n:n\geq0\}$ is the standard example of a language that is context-sensitive but not context-free.

4. Turing machines and decidability

Definition

A Turing machine is $M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\text{accept}},q_{\text{reject}})$ with an infinite tape, $\delta:Q\times\Gamma\to Q\times\Gamma\times\{L,R\}$ (state and symbol read $\to$ state, symbol to write, head direction). $M$ decides a language $L$ if it halts (in $q_{\text{accept}}$ or $q_{\text{reject}}$) on every input, accepting exactly $L$; $L$ is decidable if some TM decides it, and recognizable if some TM halts-and-accepts on exactly the strings of $L$ (possibly running forever on strings outside $L$).

The Church–Turing thesis — that Turing machines capture exactly the informal, intuitive notion of "algorithm" — is not a theorem to be proved but a claim about the relationship between an informal concept and a formal one; its evidence is that every alternative formalization proposed (lambda calculus, general recursive functions, register machines, real programming languages) has been proved computationally equivalent to Turing machines. It is universally accepted, but it is a thesis, not a theorem, and Section 5's undecidability result is a statement about Turing machines specifically, understood to be a statement about algorithms generally only via this thesis.

5. The Halting Problem is undecidable

Theorem

$HALT=\{\langle M,w\rangle : M\text{ is a TM that halts on input }w\}$ is undecidable.

Proof. Suppose some TM $H$ decides $HALT$: $H(\langle M,w\rangle)$ halts, outputting "yes" if $M$ halts on $w$ and "no" otherwise. Build a TM $D$ that, on input $\langle M\rangle$: runs $H(\langle M,M\rangle)$; if the answer is "yes" ($M$ halts on $M$), $D$ loops forever; if "no", $D$ halts. Consider running $D$ on its own description, $D(\langle D\rangle)$. If $D$ halts on $\langle D\rangle$: by construction this happens exactly when $H(\langle D,D\rangle)$ said "no", i.e. when $D$ does not halt on $D$ — contradicting that it just halted. If $D$ does not halt on $\langle D\rangle$: this happens exactly when $H(\langle D,D\rangle)$ said "yes", i.e. when $D$ does halt on $D$ — contradicting that it ran forever. Both cases are contradictions, so no TM $H$ deciding $HALT$ can exist. ∎

This is Cantor's diagonal argument in algorithmic form: $D$ is built specifically to disagree with what $H$ predicts about $D$ itself, the same self-referential trick that proves the reals are uncountable and that no set surjects onto its own power set. The Halting Problem is not "hard" in the sense $\mathrm{P}$ vs. $\mathrm{NP}$ (Section 7) problems are hard — it is not merely intractable, it is impossible for any algorithm whatsoever, with no amount of computation time ever sufficient.

6. Reductions and Rice's theorem

Section 5's proof is not just one undecidability result — it is a template. A reduction from problem $A$ to problem $B$ is an algorithm turning instances of $A$ into instances of $B$ with the same yes/no answer; if $A$ is undecidable and such a reduction exists, $B$ must be undecidable too (a decider for $B$ would give a decider for $A$, via the reduction).

Theorem (Rice's theorem, sketch)

Let $P$ be any property of languages that is non-trivial (true for some recognizable languages, false for others) and depends only on $L(M)$, not on $M$'s description. Then $\{\langle M\rangle:P(L(M))\text{ holds}\}$ is undecidable.

Proof (sketch). Assume WLOG $P(\varnothing)$ is false and some $L_0\neq\varnothing$ with $P(L_0)$ true is recognized by machine $M_0$ (the symmetric case is proved the same way, swapping accept/reject roles). Suppose $R$ decides $P$. Build $D$: on input $\langle M,w\rangle$, construct $M'$ that, on input $x$, first simulates $M$ on $w$, and — only if that halts — simulates $M_0$ on $x$ and accepts iff $M_0$ does; then run $R(\langle M'\rangle)$ and output its answer. If $M$ halts on $w$: $L(M')=L(M_0)=L_0$, which has $P$, so $R$ says yes. If $M$ does not halt on $w$: $M'$ never gets past its first step for any $x$, so $L(M')=\varnothing$, which lacks $P$, so $R$ says no. So $D$ decides $HALT$ — contradicting Section 5. ∎

Rice's theorem is a sweeping statement: any question about what a program's behavior actually computes (does it accept some string? does it accept every string? is its language finite? does it compute the same function as some other specific program?) is undecidable, the moment the question is non-trivial. The only decidable questions about a Turing machine are questions about its syntax (how many states does it have, does its code contain a certain substring) — anything about its actual runtime behavior, in general, is not decidable.

7. P, NP, and polynomial-time reductions

Definitions

$\mathrm P$ = languages decided by some TM in $O(n^k)$ time (some fixed $k$) as a function of input length $n$. $\mathrm{NP}$ = languages with a polynomial-time verifier: $L\in\mathrm{NP}$ if there is a poly-time $V$ and polynomial $q$ with $x\in L\iff\exists\,c,\,|c|\leq q(|x|),\,V(x,c)$ accepts (a "certificate" $c$ that can be checked quickly, even if finding one is hard). $A\leq_pB$ ("$A$ reduces to $B$ in polynomial time") if some poly-time computable $f$ satisfies $x\in A\iff f(x)\in B$. $B$ is NP-hard if every $A\in\mathrm{NP}$ satisfies $A\leq_pB$; $B$ is NP-complete if additionally $B\in\mathrm{NP}$.

$\mathrm P\subseteq\mathrm{NP}$ trivially (a poly-time decider is its own poly-time verifier, ignoring the certificate). Whether $\mathrm P=\mathrm{NP}$ is one of the seven Clay Millennium Prize problems and remains open; nothing below resolves it, but the machinery of NP-completeness is exactly what would let a single resolved instance settle the entire class at once (Section 12 makes this precise).

Theorem (Cook–Levin, cited without proof)

$\mathrm{3\text{-}SAT}$ — satisfiability of a Boolean formula in conjunctive normal form with exactly three literals per clause — is NP-complete.

(See Sipser, 2013, Thm. 7.37, for the full construction, which simulates an arbitrary poly-time verifier's computation history directly as a Boolean formula.) Given one NP-complete problem, polynomial-time reductions from it certify NP-hardness of anything it reduces to.

Theorem (a triangle of equivalent problems)

$S\subseteq V$ is an independent set in $G=(V,E)$ iff $V\setminus S$ is a vertex cover of $G$; $S$ is a clique in $G$ iff $S$ is an independent set in the complement graph $\bar G$.

Proof. $S$ independent means no edge of $G$ has both endpoints in $S$, i.e. every edge has at least one endpoint in $V\setminus S$ — exactly the definition of $V\setminus S$ being a vertex cover, and the argument reverses identically. $S$ is a clique in $G$ iff every pair of vertices in $S$ is an edge of $G$, iff no pair of vertices in $S$ is an edge of $\bar G$ (complementation flips every edge/non-edge), iff $S$ is independent in $\bar G$. ∎

Both equivalences are computable in polynomial time (complementing a graph, or just relabeling $S\mapsto V\setminus S$), giving $\text{Independent Set}\leq_p\text{Vertex Cover}\leq_p\text{Clique}\leq_p\text{Independent Set}$ — once one is known NP-hard, all three are.

Theorem (3-SAT $\leq_p$ Independent Set)

Given a 3-CNF formula $\phi$ with clauses $C_1,\ldots,C_m$, build $G$: one vertex per literal-occurrence (three per clause), a triangle of edges within each clause's three vertices, and an edge between any two vertices in different clauses representing a variable and its negation. Then $\phi$ is satisfiable iff $G$ has an independent set of size $m$.

Proof. ($\Rightarrow$) Given a satisfying assignment, each clause has at least one true literal; pick one such vertex per clause. No two picks are triangle-adjacent (one per triangle). No two picks are contradiction-adjacent either: that would require a literal and its negation both marked true by one assignment, impossible. So the $m$ picks form an independent set of size $m$. ($\Leftarrow$) Since each clause-triangle is a complete graph, an independent set can contain at most one vertex per triangle; achieving size $m$ over $m$ triangles forces exactly one vertex per triangle. Set each corresponding literal true (assign unconstrained variables arbitrarily); this is consistent because a contradiction-edge would have forbidden picking both a literal and its negation. Every clause has its picked literal true, so the assignment satisfies $\phi$. ∎

Figure 2 runs exactly this reduction on random 3-SAT instances and searches the resulting graph for an independent set by brute force — the reduction is a few lines of code, but the search space it hands to brute force grows explosively (Section 8).

Semilog plot of the wall-clock time to find an independent set of size m by brute force in the graph built from a random 3-SAT instance with m clauses, growing exponentially and closely tracking a 2 to the m reference curve, for m from 4 to 12.
Figure — Verifying a candidate is instant; brute-force search is not. On the exact graphs Section 7's reduction builds from random 3-SAT instances, exhaustively searching all $\binom{3m}{m}$ candidate subsets for an independent set of size $m$ takes a fraction of a millisecond at $m=4$ and over a minute at $m=12$ — twelve more clauses, forty times longer than plausible patience. Checking whether a single given subset is independent, by contrast, takes microseconds regardless of $m$: exactly the verify-fast/search-slow asymmetry the definition of $\mathrm{NP}$ is built around.

8. Computation

The figures above are generated by computability/generate_figures.py. The snippet below computes the exact Myhill-Nerode state count for $\{0^n1^n:n\leq N\}$ by enumerating reachable prefixes and their residual languages directly from the definition in Section 2 — no automaton library, no minimization algorithm, just the theorem applied literally.

def L_N(N):
    return ["0"*k + "1"*k for k in range(N+1)]

def minimal_states(N):
    lang = L_N(N)
    prefixes = {"0"*j for j in range(N+1)}
    prefixes |= {"0"*k + "1"*i for k in range(N+1) for i in range(1, k+1)}

    residuals = set()
    for w in prefixes:
        res = frozenset(s[len(w):] for s in lang if s.startswith(w))
        residuals.add(res)

    return len(residuals) + 1  # +1 for the single dead/reject class

for N in [0, 5, 10, 15, 20]:
    print(N, minimal_states(N))

Actual output:

0 2
5 12
10 22
15 32
20 42

Exactly $2N+2$ at every tested $N$, matching Figure 1's full curve — a direct, from-definitions computation of a fact that Section 2's abstract proof establishes only qualitatively (unbounded, not a specific formula).

9. Common pitfalls

Pitfall — the Pumping Lemma prover doesn't get to choose the decomposition

The lemma says: for every valid decomposition $s=xyz$ (with $|xy|\leq p$, $|y|\geq1$), pumping stays in $L$. A non-regularity proof must derive a contradiction for every such decomposition, not exhibit one convenient decomposition that happens to fail and ignore others. In Section 2's example, the constraint $|xy|\leq p$ was doing real work: it forced $y$ to lie entirely within the $0$-block, eliminating the need to separately rule out decompositions straddling the $01$ boundary.

Pitfall — the Pumping Lemma is a necessary condition for regularity, not sufficient

Satisfying the pumping property for some $p$ does not prove a language regular — some non-regular languages happen to satisfy it anyway (a well-known example: $\{ww:w\in\{0,1\}^*\}\cup\{0,1\}^*0^k1^k$-style constructions, or more simply languages built to defeat this specific lemma while remaining non-regular). The lemma is only ever used in the contrapositive direction, to disprove regularity, exactly as in Section 2 — never to prove it.

Pitfall — undecidable means no algorithm ever, not "no algorithm known yet"

Section 5's proof is a proof, not a report of failed attempts — it shows every possible TM $H$ fails, not that today's best TMs fail. This coexists with the fact that most individual instances of the Halting Problem are easy (a loop with no exit condition obviously never halts); undecidability is a statement about the impossibility of one algorithm handling every instance correctly, not a claim that every instance is individually mysterious.

Pitfall — NP-hard does not mean "in NP," and NP-complete is the stronger, more specific claim

Section 7 defines NP-hardness as "every NP problem reduces to it" without requiring membership in $\mathrm{NP}$ itself. The Halting Problem (Section 5) is a genuine example of the gap: it is NP-hard (3-SAT reduces to it — given a formula $\phi$, build in polynomial time a TM that brute-force-checks every assignment and halts the moment it finds one satisfying $\phi$, looping forever only if none exists, so this TM halts iff $\phi$ is satisfiable), yet it is not in $\mathrm{NP}$ at all, since it is not even decidable, let alone verifiable in polynomial time. "NP-complete" — the conjunction of NP-hard and in $\mathrm{NP}$ — is the strictly more specific and more commonly intended claim for problems like 3-SAT and Independent Set, and it is not automatic from NP-hardness alone.

10. Connections

11. References