What Theory of Computation Asks

Theory of computation studies two questions: what can be computed at all (computability), and how efficiently (complexity). It builds a ladder of abstract machines — from simple finite automata to Turing machines — each recognising a larger class of languages. A language is just a set of strings over an alphabet Σ, and computation is reframed as deciding membership in a language.

The Chomsky Hierarchy

Language class	Machine	Grammar	Example
Regular	DFA / NFA	Regular (Type-3)	ab
Context-free	Pushdown automaton	CFG (Type-2)	aⁿbⁿ, balanced parens
Context-sensitive	Linear-bounded TM	CSG (Type-1)	aⁿbⁿcⁿ
Recursively enumerable	Turing machine	Unrestricted (Type-0)	Halting problem

Each level strictly contains the ones below

Every regular language is context-free, every context-free language is context-sensitive, and so on. The containments are strict: aⁿbⁿ is context-free but not regular, and aⁿbⁿcⁿ is context-sensitive but not context-free. More powerful machines recognise more languages.

Finite Automata

A deterministic finite automaton (DFA) is the simplest model: finite memory (just its current state), reads input left to right, and accepts if it ends in an accepting state. Formally it is a 5-tuple (Q, Σ, δ, q₀, F): states, alphabet, transition function, start state, accepting states.

// DFA accepting binary strings with an EVEN number of 0s
//  States: {even, odd}  (parity of 0s seen so far)
//  Start: even   Accepting: {even}

         0            0
   ┌──────────┐  ┌──────────┐
   ▼          │  ▼          │
[even] ──0──> [odd] ──0──> [even]
   │  ▲                       ▲ │
   1  └─────────1─────────────┘ 1   (1 is a self-loop on each state)

δ(even, 0) = odd    δ(odd, 0) = even
δ(even, 1) = even   δ(odd, 1) = odd

A nondeterministic finite automaton (NFA) may have several transitions on the same symbol and ε-transitions (moves without consuming input). It accepts if any computation path reaches an accepting state. NFAs are often far smaller and easier to build from a regex.

DFA and NFA are equally powerful

Nondeterminism adds convenience, not power. Every NFA can be converted to an equivalent DFA by the subset construction: each DFA state is a set of NFA states. The DFA may have up to 2ⁿ states, but it recognises exactly the same language.

Regular Languages & Regular Expressions

The regular languages are exactly those recognised by finite automata — and equivalently, those describable by regular expressions and by regular grammars. This triple equivalence (Kleene's theorem) is a cornerstone result.

// Regular expression operators
a          single symbol
a | b      union (a or b)
ab         concatenation
a*         Kleene star (zero or more a)
a+         one or more a           = aa*
(ab)*      grouping

// Examples
(0|1)*        every binary string
(0|1)*01      binary strings ending in 01
a*b*          zero+ a's then zero+ b's

Regular languages are closed under union, intersection, complement, concatenation, and Kleene star — a useful fact for proofs. But finite automata cannot count arbitrarily, which is exactly why some languages fall outside this class.

The Pumping Lemma for Regular Languages

The pumping lemma proves a language is not regular. If L is regular, there is a pumping length p such that any string s in L with |s| ≥ p can be split as s = xyz where |y| ≥ 1, |xy| ≤ p, and xyⁱz ∈ L for all i ≥ 0. Intuitively, a long enough string forces the DFA to repeat a state, creating a loop you can pump.

// Prove L = { aⁿbⁿ : n ≥ 0 } is NOT regular
1. Assume L is regular with pumping length p.
2. Choose s = aᵖbᵖ  (in L, length ≥ p).
3. Any split s = xyz with |xy| ≤ p means y is all a's (y = aᵏ, k ≥ 1).
4. Pump: xy²z = aᵖ⁺ᵏ bᵖ  has more a's than b's, so it is NOT in L.
5. Contradiction — therefore L is not regular. ∎

Context-Free Grammars & Pushdown Automata

A context-free grammar (CFG) has productions of the form A → γ where A is a single nonterminal. CFGs describe nested, recursive structure — arithmetic expressions, balanced parentheses, and most programming-language syntax.

// CFG for balanced parentheses
S -> ( S ) S  |  ε

// Derivation of "(())()"
S => (S)S => ((S)S)S => (()S)S => (())S => (())(S)S => (())()

// CFG for aⁿbⁿ — not regular, but easily context-free
S -> a S b  |  ε

A pushdown automaton (PDA) is a finite automaton augmented with a stack. The stack gives it unbounded memory with last-in-first-out access — exactly enough to match nested structure. PDAs recognise precisely the context-free languages.

// PDA recognising aⁿbⁿ
On 'a': push X onto the stack
On 'b': pop one X off the stack
Accept if the stack is empty (and all input consumed)
// The stack "counts" the a's so it can match them against the b's

Why one stack isn't enough for aⁿbⁿcⁿ

A single stack can match a's against b's, but by the time it has emptied to check the b's it has forgotten how many a's there were, so it can't also match c's. The pumping lemma for context-free languages (which pumps two substrings v and y simultaneously) proves aⁿbⁿcⁿ is not context-free.

Turing Machines

A Turing machine (TM) has a finite control plus an infinite tape it can read, write, and move over in both directions. This unbounded, random-access memory makes it the most powerful standard model. The Church-Turing thesis holds that anything intuitively computable can be computed by a Turing machine — every reasonable model (lambda calculus, register machines, real computers) is equivalent in power.

// TM as a 7-tuple
(Q, Σ, Γ, δ, q₀, q_accept, q_reject)
  Q       states
  Σ       input alphabet
  Γ       tape alphabet (includes blank ⊔)
  δ       Q × Γ -> Q × Γ × {L, R}   (state, read) -> (state, write, move)
  q₀      start state

// A TM can LOOP FOREVER. Three outcomes: accept, reject, or never halt.

Two important language classes emerge from what a TM can do:

Decidable (recursive): a TM halts on every input, always answering yes or no. This corresponds to problems with a guaranteed algorithm.
Recognisable (recursively enumerable): a TM halts and accepts on yes-instances, but may loop forever on no-instances.

Decidability & the Halting Problem

Some problems have no algorithm at all. The most famous is the halting problem: given a program P and input x, does P halt on x? Turing proved this is undecidable — no TM can decide it for all inputs.

// Diagonalization proof sketch
Assume H(P, x) decides whether program P halts on input x.
Build D(P):
    if H(P, P) says "halts"  then loop forever
    else                     then halt
Now run D(D):
    D(D) halts   => H says D(D) halts => D loops forever   (contradiction)
    D(D) loops   => H says it doesn't => D halts           (contradiction)
=> H cannot exist. The halting problem is undecidable. ∎

Reductions spread undecidability: if a known-undecidable problem A reduces to problem B (an algorithm for B would solve A), then B is undecidable too. Rice's theorem generalises this — any nontrivial property of the language a program computes is undecidable.

Complexity: P vs NP

Among decidable problems, we classify by resource use. P is the class of problems solvable in polynomial time. NP is the class whose yes-answers can be verified in polynomial time given a certificate (equivalently, solved by a nondeterministic TM in polynomial time).

Class	Meaning	Example
P	Solvable in poly time	Sorting, shortest path, 2-SAT
NP	Verifiable in poly time	SAT, subset-sum, Hamiltonian path
NP-complete	Hardest in NP; all NP reduces to it	SAT, 3-SAT, TSP (decision), clique
NP-hard	At least as hard as NP-complete	Halting problem, TSP optimisation

Clearly P ⊆ NP. Whether P = NP — whether every quickly-verifiable problem is also quickly solvable — is the biggest open question in computer science. A problem is NP-complete if it is in NP and every NP problem reduces to it (Cook-Levin proved SAT is the first such problem). If any NP-complete problem were in P, then P = NP.

Why it matters in practice

If a problem is NP-complete, don't expect an exact polynomial algorithm — reach instead for heuristics, approximation algorithms, or exponential solvers that are fast enough on real instances. Recognising NP-completeness (often by reduction from SAT or 3-SAT) tells you to stop hunting for a fast exact solution.

Practice Exercises

Design a DFA over {0,1} that accepts strings whose numeric value is divisible by 3.
Convert the NFA for (a|b)*abb into a DFA using the subset construction.
Use the pumping lemma to prove that the language of palindromes over {a,b} is not regular.
Write a context-free grammar for arithmetic expressions with +, *, and parentheses that encodes precedence.
Describe a Turing machine that decides whether an input string has the form aⁿbⁿcⁿ.
Show that the problem "does program P ever print the string HELLO?" is undecidable by reducing from the halting problem.