What You Will Find Here: Every key fact, formula, conversion rule, closure property, decidability result, and complexity class relationship in Theory of Computation — organised for quick lookup. Includes the Chomsky Hierarchy, DFA/NFA properties, pumping lengths, NP-Complete reduction chain, and the decidability table.
1. Chomsky Hierarchy
Type
Language
Grammar Rule Form
Machine
Example
Type 3
Regular
A → aB or A → a
DFA / NFA
a*b, identifiers
Type 2
Context-Free
A → α (any string)
PDA
{anbn}, program syntax
Type 1
Context-Sensitive
|lhs| ≤ |rhs|
Linear-Bounded Automaton
{anbncn}
Type 0
Recursively Enumerable
Unrestricted
Turing Machine
ATM
Containment: Regular ⊂ CFL ⊂ CSL ⊂ RE. Each containment is strict.
2. DFA & NFA Key Facts
Property
DFA
NFA
Transitions per state per symbol
Exactly 1
0, 1, or many
Epsilon transitions
Not allowed
Allowed
Power (languages recognised)
Regular
Regular (same as DFA)
States after NFA → DFA
Up to 2n (n = NFA states)
n
Acceptance
In accept state after all input
Any path reaches accept state
Minimisation
Minimal DFA states = number of Myhill-Nerode equivalence classes of L
Key Conversions
From
To
Method
NFA
DFA
Subset (powerset) construction — track sets of NFA states
Regex
NFA
Thompson’s construction (build inductively)
DFA
Regex
State elimination (remove states, annotate transitions)
DFA
Minimal DFA
Table-filling (Myhill-Nerode) — merge equivalent states
3. Regular Expression Laws
Law
Expression
Identity for union
R + ∅ = R
Identity for concatenation
Rε = εR = R
Annihilator for concatenation
R∅ = ∅R = ∅
Idempotence of union
R + R = R
Commutativity of union
R + S = S + R
Associativity of union
(R+S)+T = R+(S+T)
Associativity of concatenation
(RS)T = R(ST)
Distributivity
R(S+T) = RS+RT
Star of star
(R*)* = R*
Star decomposition
R* = ε + R + RR + RRR + …
Arden’s Lemma
If X = RX + S then X = R*S (unique solution if ε ∉ L(R))
4. Pumping Lemmas
For Regular Languages
w = xyz, |xy| ≤ p, |y| ≥ 1, xyiz ∈ L for all i ≥ 0
The pumping constant p is at most the number of states in the minimal DFA for L.
For Context-Free Languages
w = uvxyz, |vxy| ≤ p, |vy| ≥ 1, uvixyiz ∈ L for all i ≥ 0
Both v and y are “pumped” together. Since |vxy| ≤ p, they span at most two symbol types in structured languages.
Using the Pumping Lemma (Proof Checklist)
Assume L is regular/CFL (for contradiction)
Let p be the pumping length
You choose a specific w ∈ L with |w| ≥ p — choose cleverly so all splits cause problems
For all valid splits, show pumping escapes L (at i=0 or i=2 usually works)
Contradiction — L is not regular/CFL
5. Closure Properties
Operation
Regular
CFL
Decidable
RE (semi-decidable)
Union
Yes
Yes
Yes
Yes
Intersection
Yes
No
Yes
Yes
Complement
Yes
No
Yes
No
Concatenation
Yes
Yes
Yes
Yes
Kleene Star
Yes
Yes
Yes
Yes
Difference (L1−L2)
Yes
No
Yes
No
Reversal
Yes
Yes
Yes
Yes
Homomorphism
Yes
Yes
Yes
Yes
Inverse Homomorphism
Yes
Yes
Yes
Yes
Intersection with Regular
Yes
Yes
Yes
Yes
Key trick: CFL ∩ Regular = CFL (intersecting a CFL with a regular language gives a CFL — useful in compiler design to add keyword restrictions).
6. CFG & PDA Key Facts
Property
Detail
Equivalent models
CFG = PDA = Context-Free Languages
CNF rule forms
A → BC (two non-terminals) or A → a (one terminal)
CYK complexity
O(n3 |G|) — requires CNF
DPDA vs PDA
Deterministic PDA recognises strict subset of CFLs
Inherently ambiguous
Some CFLs have no unambiguous grammar
ECFG (is CFL empty?)
Decidable
ACFG (does CFG generate w?)
Decidable (CYK)
EQCFG (do two CFGs generate same language?)
Undecidable
Ambiguity of a CFG
Undecidable
CNF Conversion Steps (in order)
New start symbol S0 → S
Eliminate ε-rules (handle nullable variables)
Eliminate unit rules (A → B)
Break long rules (A → B1B2…Bk, k ≥ 3)
Move terminals out of binary rules (A → aB becomes A → NaB, Na → a)
7. Decidability Quick Reference
Problem
Description
Decidable?
RE?
ADFA
Does DFA M accept w?
Yes
Yes
EDFA
Is L(DFA M) empty?
Yes
Yes
EQDFA
Do two DFAs accept same language?
Yes
Yes
ACFG
Does CFG G generate w?
Yes
Yes
ECFG
Is L(CFG G) empty?
Yes
Yes
EQCFG
Do two CFGs generate same language?
No
No
ATM
Does TM M accept w?
No
Yes
HALTTM
Does TM M halt on w?
No
Yes
ETM
Is L(TM M) empty?
No
No
EQTM
Do two TMs accept same language?
No
No
REGULARTM
Is L(M) a regular language?
No
No
PCP
Post Correspondence Problem
No
Yes
Key Decidability Facts
L is decidable ⇔ both L and complement(L) are RE
ATM is RE but not decidable (complement of ATM is not RE)
ETM is not RE (neither is its complement)
Every non-trivial semantic property of TMs is undecidable (Rice’s Theorem)
8. Complexity Class Summary
Class
Definition
Known Relationship
P
Decidable in O(nk) time (deterministic)
P ⊆ NP
NP
Solutions verifiable in O(nk) time
NP ⊆ PSPACE
co-NP
Complements of NP problems
P ⊆ NP ∩ co-NP
NP-Complete
NP ∩ NP-Hard
In NP, every NP problem reduces to it
NP-Hard
Every NP problem reduces to it
May or may not be in NP
PSPACE
Decidable in polynomial space
P ⊆ NP ⊆ PSPACE ⊆ EXPTIME
EXPTIME
Decidable in 2poly(n) time
P ≠ EXPTIME (proved)
9. NP-Complete — Reduction Chain
CIRCUIT-SAT ↓ (Cook-Levin, 1971) SAT (Boolean Satisfiability) ↓ 3-SAT (3-literal clauses) ↓ ↓ ↓ Clique Independent Set Vertex Cover ↓ Hamiltonian Cycle → TSP (decision) ↓ 3-Coloring Subset Sum Bin Packing
Important NP-Complete Problems — One-Line Summary
Problem
Input
Question
SAT
Boolean formula
Satisfying assignment?
3-SAT
CNF with ≤3 literals/clause
Satisfying assignment?
Clique
Graph G, integer k
Complete subgraph of size k?
Vertex Cover
Graph G, integer k
k vertices covering all edges?
Independent Set
Graph G, integer k
k mutually non-adjacent vertices?
Hamiltonian Cycle
Graph G
Cycle visiting all vertices once?
TSP (decision)
Weighted graph, integer k
Tour of all cities with cost ≤ k?
3-Coloring
Graph G
Colour with 3 colours, no same-colour adjacent?
Subset Sum
Set S, target T
Subset of S summing to exactly T?
Partition
Set S of integers
Partition S into two equal-sum halves?
10. Frequently Asked Questions
What is the pumping length p in the Pumping Lemma for regular languages?
The pumping length p is at least the number of states in the minimal DFA for the language. The formal guarantee is that any string of length ≥ p must contain a repeatable section. When using the lemma to prove non-regularity, you treat p as an unknown constant — you choose a string in terms of p, then show pumping breaks the language regardless of what p’s actual value is.
Why is EQ_CFG undecidable but EQ_DFA decidable?
For DFAs, you can construct the DFA for the symmetric difference L1 Δ L2 and check if it is empty — all these operations (complement, intersection, emptiness testing) are decidable for regular languages. For CFGs, complement and intersection are not closed operations on CFLs, so you cannot construct a CFG for the symmetric difference. The undecidability of EQCFG follows by reduction from the halting problem.
How do I remember which closure properties CFLs do NOT have?
Remember the counterexample: L1 = {anbncm} and L2 = {ambncn} are both CFLs. Their intersection L1 ∩ L2 = {anbncn} is not CFL. Since complement(L) = Σ* minus L, if CFLs were closed under complement, they would be closed under intersection (via De Morgan) — but they aren’t. So CFLs are not closed under complement either. CFLs ARE closed under intersection with a regular language — only CFL ∩ CFL can fail.
What are the key differences between the Pumping Lemma for regular languages and for CFLs?
Regular: w = xyz, pump y (one segment in the first p characters). CFL: w = uvxyz, pump v and y together (two segments, total length of vxy ≤ p). The CFL version is harder to apply because the adversary can place the vxy window anywhere in the string — you must show pumping escapes the language for every possible placement, not just the obvious one. For the CFL version, common choices are strings with three equal blocks (like apbpcp) where any two-point pump disrupts the balance.