Theory of Computation Cheat Sheet

Automata Theory

Automaton	Memory	Language Class	Accepts	Example
Finite Automaton (FA)	No memory	Regular Languages	Regular expressions, simple patterns	Strings ending with '01'
Pushdown Automaton (PDA)	Stack memory	Context-Free Languages	Balanced parentheses, palindromes	Strings with equal 0s and 1s
Linear Bounded Automaton (LBA)	Limited tape	Context-Sensitive Languages	Context-sensitive grammars	anbncn
Turing Machine (TM)	Infinite tape	Recursively Enumerable Languages	All computable functions	Any algorithmic problem

Chomsky Hierarchy

Type	Grammar	Automaton	Production Rules	Example Language
Type-0	Unrestricted	Turing Machine	α → β (α contains at least one non-terminal)	All recursively enumerable languages
Type-1	Context-Sensitive	Linear Bounded Automaton	αAβ → αγβ (\|γ\| ≥ \|A\|)	{anbncn \| n ≥ 1}
Type-2	Context-Free	Pushdown Automaton	A → α (A is non-terminal)	Palindromes, arithmetic expressions
Type-3	Regular	Finite Automaton	A → aB or A → a (right-linear)	Strings ending with '01', even numbers

Regular Languages

Concept	Description	Properties	Operations
Regular Expression	Pattern for describing regular languages	Closed under union, concatenation, Kleene star	Union (∪), concatenation (.), Kleene star (*)
Finite Automaton	Machine with finite states	Deterministic and non-deterministic equivalent	Union, intersection, complement
Myhill-Nerode Theorem	Criterion for regularity	Finite number of equivalence classes	Minimization of DFA
Pumping Lemma	Tool to prove non-regularity	For regular L, ∃ p such that ∀ s ∈ L with \|s\| ≥ p, s = xyz, \|xy\| ≤ p, \|y\| ≥ 1, xyiz ∈ L ∀ i ≥ 0	Proving languages non-regular

Context-Free Languages

Concept	Description	Properties	Applications
Context-Free Grammar (CFG)	Rules of form A → α where A is non-terminal	Chomsky Normal Form, Greibach Normal Form	Programming language syntax, parsing
Pushdown Automaton (PDA)	FA with stack memory	Deterministic and non-deterministic not equivalent	Compiler design, syntax analysis
CYK Algorithm	Dynamic programming for CFG parsing	O(n³) time complexity	Recognition of CFL
Pumping Lemma	Tool to prove non-CFL	For CFL L, ∃ p such that ∀ s ∈ L with \|s\| ≥ p, s = uvxyz, \|vxy\| ≤ p, \|vy\| ≥ 1, uvixyiz ∈ L ∀ i ≥ 0	Proving languages non-CFL

Turing Machines

Variant	Description	Power	Equivalence
Standard TM	One-way infinite tape, read/write head	Most powerful computational model	Equivalent to other variants
Multi-tape TM	Multiple tapes with independent heads	Same power as standard TM	Can simulate standard TM
Non-deterministic TM	Multiple possible transitions	Same power as deterministic TM	Can be simulated by deterministic TM
Multi-dimensional TM	Tape arranged in multiple dimensions	Same power as standard TM	Can simulate standard TM
Universal TM	TM that simulates any other TM	Can compute any computable function	Foundation of modern computers

Decidability

Class	Description	Examples	Properties
Decidable (Recursive)	Turing machine halts and accepts/rejects all inputs	Regular languages, Context-free languages	Closed under complement, union, intersection
Undecidable (Recursively Enumerable)	Turing machine accepts all strings in the language but may not halt on non-members	Halting problem, Post correspondence problem	Not closed under complement
Not Recursively Enumerable	No Turing machine can recognize the language	Complement of halting problem	No algorithm exists

Undecidable Problems

Problem	Description	Why Undecidable	Significance
Halting Problem	Determine if TM halts on given input	Diagonalization argument, self-reference	Fundamental result in computability
Post Correspondence Problem	Find sequence of dominoes with matching top/bottom strings	Can encode computation of TMs	Useful for proving other problems undecidable
Emptiness Problem	Determine if language accepted by TM is empty	Reduction from halting problem	Important for program analysis
Equivalence Problem	Determine if two TMs accept same language	Reduction from emptiness problem	Important for program verification
Membership Problem	Determine if string is in language of given TM	Reduction from halting problem	Generalization of halting problem

Complexity Classes

Class	Definition	Characteristics	Examples
P	Problems solvable in polynomial time by deterministic TM	Efficiently solvable	Shortest path, sorting, primality testing
NP	Problems solvable in polynomial time by non-deterministic TM	Solutions verifiable in polynomial time	TSP, graph coloring, SAT
NP-Complete	NP problems to which all other NP problems reduce in polynomial time	Hardest problems in NP	SAT, 3-SAT, vertex cover, TSP
NP-Hard	Problems to which all NP problems reduce in polynomial time	At least as hard as NP-complete	TSP optimization, halting problem
PSPACE	Problems solvable in polynomial space	Contains P and NP	Quantified Boolean formulas
EXP	Problems solvable in exponential time	Contains P and NP	Generalized chess

Reductions

Type	Description	Purpose	Method
Polynomial Reduction	Transform instance of problem A to instance of problem B in polynomial time	Prove problem B is at least as hard as A	Construct function f such that x ∈ A iff f(x) ∈ B
Many-one Reduction	Each instance of A maps to single instance of B	Compare complexity of decision problems	Function f is computable and x ∈ A iff f(x) ∈ B
Turing Reduction	Problem A solved using algorithm for B as subroutine	More general than many-one reduction	Algorithm for A uses B as oracle

Key Theorems and Results

Theorem	Statement	Significance	Applications
Kleene's Theorem	Regular expressions, finite automata, and regular grammars are equivalent	Foundation of formal language theory	Compiler design, pattern matching
Pumping Lemma for Regular Languages	Regular languages satisfy the pumping property	Tool to prove languages non-regular	Proving undecidability of certain problems
Cook's Theorem	SAT is NP-complete	First NP-complete problem	Foundation of NP-completeness theory
Rice's Theorem	All non-trivial properties of recursively enumerable languages are undecidable	General result about undecidability	Proving many problems undecidable
Church-Turing Thesis	Intuitive notion of computation equals Turing machine computation	Foundation of computability theory	Defines limits of computation