Theory of Computation Quick Reference
Everything you need day‑to‑day – automata, languages, and complexity.
Chomsky Hierarchy
| Grammar | Automaton | Language | Example |
|---|---|---|---|
| Type 0 – Unrestricted | Turing Machine | Recursively Enumerable | Any computable problem |
| Type 1 – Context‑Sensitive | Linear Bounded Automaton | Context‑Sensitive | aⁿbⁿcⁿ |
| Type 2 – Context‑Free | Pushdown Automaton (PDA) | Context‑Free | aⁿbⁿ |
| Type 3 – Regular | Finite Automaton (DFA/NFA) | Regular | a* b* |
Hierarchy Inclusions
- Regular ⊂ Context‑Free ⊂ Context‑Sensitive ⊂ Recursively Enumerable
- Every regular language is context‑free, but not vice versa
- Every context‑free language is context‑sensitive (except ε)
Finite Automata
DFA (Deterministic Finite Automaton)
- 5‑tuple: (Q, Σ, δ, q₀, F)
- Q – finite set of states
- Σ – finite alphabet
- δ – Q × Σ → Q (transition function)
- q₀ – start state
- F – set of accepting states
- Deterministic – exactly one transition per symbol
NFA (Nondeterministic Finite Automaton)
- 5‑tuple: (Q, Σ, δ, q₀, F)
- δ – Q × Σ → 2^Q (set of states)
- Multiple transitions possible
- ε‑transitions allowed (NFA‑ε)
- Every NFA can be converted to DFA
- DFA and NFA recognise the same languages
DFA vs NFA
| Aspect | DFA | NFA |
|---|---|---|
| Transitions | Single per symbol | Multiple per symbol |
| ε‑transitions | No | Yes (optional) |
| States | More (exponential worst‑case) | Fewer |
| Implementation | Easier | Harder |
| Recognition | Simulate directly | Backtracking or subset construction |
Regular Languages
- Languages accepted by finite automata
- Described by regular expressions
- Closed under: union, concatenation, Kleene star, intersection, complement, difference
Pumping Lemma for Regular Languages
If L is regular, ∃ p (pumping length) such that ∀ w ∈ L with |w| ≥ p:
w = xyz, where: 1. |xy| ≤ p 2. |y| ≥ 1 3. xyⁱz ∈ L ∀ i ≥ 0
Use: To prove a language is NOT regular (by contradiction).
Context‑Free Grammars
CFG Components
- G = (V, Σ, R, S)
- V – variables (non‑terminals)
- Σ – terminals
- R – production rules (A → α)
- S – start symbol
Chomsky Normal Form (CNF)
- All productions are of the form:
- A → BC (exactly two variables)
- A → a (one terminal)
- S → ε (optional, only start symbol)
- Every CFG can be converted to CNF
Greibach Normal Form (GNF)
- Productions: A → aα (terminal followed by variables)
- Used for deriving from left to right
Context‑Free Languages
- Languages accepted by PDAs
- Generated by CFGs
- Closed under: union, concatenation, Kleene star, reversal
- Not closed under: intersection, complement
Ambiguity
- A grammar is ambiguous if there exists a string with ≥ 2 parse trees
- Inherently ambiguous – every grammar for the language is ambiguous
Pumping Lemma for CFL
If L is CFL, ∃ p such that ∀ w ∈ L with |w| ≥ p:
w = uvxyz, where: 1. |vxy| ≤ p 2. |vy| ≥ 1 3. uvⁱxyⁱz ∈ L ∀ i ≥ 0
Pushdown Automata (PDA)
PDA Components
- 6‑tuple: (Q, Σ, Γ, δ, q₀, F)
- Q – states
- Σ – input alphabet
- Γ – stack alphabet
- δ – Q × Σ × Γ → Q × Γ*
- q₀ – start state
- F – final states
Types of PDA
- DPDA – Deterministic PDA
- NPDA – Nondeterministic PDA
- DPDA accepts deterministic CFL
- NPDA accepts all CFL
- DPDA ⊂ NPDA (strict)
Acceptance
- Final state – reach accepting state after reading input
- Empty stack – stack is empty after reading input
- Both are equivalent for PDAs
Equivalence
- CFG ↔ PDA (both describe the same class of languages)
- Every CFG has an equivalent PDA
- Every PDA has an equivalent CFG
Turing Machines
TM Components
- 7‑tuple: (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
- Q – finite set of states
- Σ – input alphabet (not including blank)
- Γ – tape alphabet (Σ ⊂ Γ, blank ∈ Γ)
- δ – Q × Γ → Q × Γ × {L, R}
- q₀ – start state
- q_accept – accept state
- q_reject – reject state
TM Variants
- Multi‑tape – multiple tapes, equivalent to single‑tape
- Nondeterministic – multiple possible transitions, equivalent to deterministic
- Oracle – can query an external oracle
- Universal TM – can simulate any other TM
- Linear Bounded Automaton – TM with bounded tape (context‑sensitive)
Turing Machine Operations
- Read symbol from tape
- Write symbol to tape
- Move head Left or Right
- Change state
- Loop until accept or reject
Decidability & Undecidability
Decidable Languages
- There exists a Turing Machine that halts on all inputs
- Accepts if string ∈ L, rejects if string ∉ L
- Examples: Regular languages, CFLs, some CSLs
- Membership: finite automata, CFG parsing
- Properties of finite automata (emptiness, equivalence)
Undecidable Languages
- No TM can decide membership
- May be accepted by a TM that doesn't halt for some inputs
- Examples: Halting Problem, Post Correspondence
- Emptiness of context‑free languages?
- Ambiguity of CFG
- Equality of CFLs
Halting Problem
- Does TM M halt on input w?
- Undecidable – no algorithm can decide
- Proof by contradiction using diagonalization
Rice's Theorem
- Any non‑trivial property of recursively enumerable languages is undecidable
- Non‑trivial = not always true or always false
- Examples: Is L(M) empty? Is L(M) regular? Does M halt?
- All are undecidable
Reducibility
- Language A reduces to B (A ≤ B)
- If A ≤ B and B is decidable, then A is decidable
- If A ≤ B and A is undecidable, then B is undecidable
- Mappings, Turing reductions, oracle reductions
Complexity Classes
Time Complexity
- P – solvable in polynomial time O(nᵏ)
- NP – verifiable in polynomial time
- EXP – exponential time O(2ⁿ)
- NP‑Complete – hardest problems in NP
- NP‑Hard – at least as hard as NP
Space Complexity
- L – logarithmic space O(log n)
- PSPACE – polynomial space
- NPSPACE – nondeterministic polynomial space
- PSPACE = NPSPACE (Savitch's theorem)
- P ⊆ NP ⊆ PSPACE ⊆ NPSPACE ⊆ EXP
Important Theorems
- P =? NP – unsolved millennium problem
- Cook‑Levin – SAT is NP‑Complete
- Savitch's – NSPACE(s) ⊆ SPACE(s²)
- Immerman‑Szelepcsényi – NSPACE = co‑NSPACE
- Time Hierarchy – more time gives more power
- Space Hierarchy – more space gives more power
Common NP‑Complete Problems
- SAT (Boolean Satisfiability)
- 3‑SAT
- Clique
- Vertex Cover
- Independent Set
- Travelling Salesman (decision version)
- Hamiltonian Cycle
- Graph Colouring
- Subset Sum
- Knapsack
Decidability Summary
| Problem | Decidable? | Note |
|---|---|---|
| Membership for DFA | Yes | Simulate DFA |
| Membership for CFG | Yes | CYK algorithm (O(n³)) |
| Emptiness for DFA | Yes | Reachability of final state |
| Emptiness for CFG | Yes | Check for non‑terminal derivation |
| Equivalence for DFA | Yes | Minimization and comparison |
| Equivalence for CFG | No | Undecidable |
| Ambiguity for CFG | No | Undecidable |
| Halting Problem | No | Classic undecidable |
| Post Correspondence | No | Undecidable |
| All non‑trivial CFG properties | No | Rice's theorem |
📌 Quick Reference
Chomsky Hierarchy: Type 0 (TM) ⊃ Type 1 (LBA) ⊃ Type 2 (PDA) ⊃ Type 3 (DFA/NFA)
Regular: DFA/NFA, regex, pumping lemma (pumping length)
Context‑Free: CFG, PDA, CNF, GNF, pumping lemma
Turing Machine: any computable function, halt/accept/reject
P vs NP: open problem, NP‑Complete (SAT, 3‑SAT, Clique, etc.)
Decidable: membership, emptiness for DFA/CFG
Undecidable: Halting, PCP, Rice's theorem
Mapping: A ≤ B (reduce A to B)
Regular: DFA/NFA, regex, pumping lemma (pumping length)
Context‑Free: CFG, PDA, CNF, GNF, pumping lemma
Turing Machine: any computable function, halt/accept/reject
P vs NP: open problem, NP‑Complete (SAT, 3‑SAT, Clique, etc.)
Decidable: membership, emptiness for DFA/CFG
Undecidable: Halting, PCP, Rice's theorem
Mapping: A ≤ B (reduce A to B)