Theory of Computation Cheatsheet

Chomsky Hierarchy

Strict containment: Regular ⊂ CF ⊂ CS ⊂ RE.

Finite Automata

DFA 5-tuple

(Q, Σ, δ, q₀, F)
  δ: Q × Σ -> Q          exactly one transition per (state, symbol)
NFA: δ may map to a SET of states + ε-moves; accept if ANY path accepts

Regular Expressions

a|b   union        ab   concat      a*   zero+      a+   one+
Kleene's theorem:  regex ≡ NFA ≡ DFA ≡ regular grammar

Closure (regular): union, intersection, complement, concat, star
(0|1)*01    ends in 01
a*b*        a's then b's

Pumping Lemma (Regular)

L regular => ∃p, every s∈L with |s|≥p splits s = xyz where
   |y| ≥ 1,  |xy| ≤ p,  and  xyⁱz ∈ L for all i ≥ 0
Use it to DISPROVE regularity (e.g. aⁿbⁿ: pump the a's, breaks balance).

CFG & PDA

CFG production:  A -> γ    (single nonterminal on the left)

Balanced parens:  S -> ( S ) S | ε
aⁿbⁿ:             S -> a S b | ε

PDA = NFA + stack (LIFO). Recognises exactly the CFLs.
  aⁿbⁿ:  push on 'a', pop on 'b', accept on empty stack

CFL pumping lemma pumps TWO substrings (v,y) at once
  => disproves aⁿbⁿcⁿ being context-free

Turing Machines & Decidability

TM 7-tuple: (Q, Σ, Γ, δ, q₀, q_acc, q_rej)
  δ: Q × Γ -> Q × Γ × {L,R}     read/write/move, infinite tape

Church-Turing thesis: TM = everything intuitively computable

Decidable (recursive)   : TM halts on ALL inputs (yes/no)
Recognisable (RE)       : halts+accepts on YES, may loop on NO

Halting problem = UNDECIDABLE  (diagonalization)
Rice's theorem  = any nontrivial property of a program's language = undecidable
Reductions: A ≤ B and A undecidable  =>  B undecidable

Complexity Classes

P ⊆ NP.  P = NP is OPEN.
Cook-Levin: SAT is NP-complete (the first one).
Prove X NP-complete: (1) X ∈ NP  (2) reduce a known NPC problem to X.
NP-complete in practice => use heuristics / approximation / SAT solvers.