Notes
Every high-yield formula, closure property, decidability result, normal-form bound, and witness language across Phases 0–5 consolidated in one place. Use Rules & Shortcuts to filter individual lesson cards.
1Phase-by-Phase Core Rule Cards
- Sets & counting: |P(A)| = 2|A|; |A × B| = |A|·|B|; #functions A → B = |B||A|; #relations on n-set = 2n². |∅| = 0, |{∅}| = 1, |{ε}| = 1.
- Equivalence relations: reflexive + symmetric + transitive; equivalence classes partition the set; number of classes = index.
- Strings & languages over Σ (|Σ| = k): |Σn| = kn; strings of length ≤ n = (kn+1 − 1)/(k − 1). |uv| = |u| + |v|; (uv)R = vRuR.
- Substrings vs prefixes/suffixes: For |w| = n with all distinct symbols: prefixes = n + 1, suffixes = n + 1, non-empty substrings = n(n+1)/2, total substrings (with ε) = n(n+1)/2 + 1.
- Edge cases: L · {ε} = L; L · ∅ = ∅; ∅* = {ε}; {ε}* = {ε}; L0 = {ε}; L+ = LL*; L* = L+ ∪ {ε} (so L+ = L* iff ε ∈ L).
- DFA: M = (Q, Σ, δ, q₀, F) with total δ : Q × Σ → Q. Always halts in |w| steps. ε ∈ L(M) ⇔ q₀ ∈ F. GATE counts the dead/trap state in minimal-DFA state counts.
- NFA & ε-NFA: δ : Q × Σ → P(Q) (or Q × (Σ ∪ {ε}) → P(Q)). Accepts if some path ends in F. Subset construction gives an equivalent DFA with ≤ 2n states (only reachable subsets counted; ∅ becomes the dead state if reached).
- Product construction (n₁ and n₂ states): ≤ n₁·n₂ states. Union: F = (F₁×Q₂) ∪ (Q₁×F₂); Intersection: F = F₁×F₂; Difference L₁ − L₂: F = F₁×(Q₂−F₂); Complement of complete DFA: F' = Q − F (fails on NFAs without determinizing first).
- Minimization & Myhill–Nerode: (1) Remove unreachable states first; (2) Partition refinement from P₀ = {F, Q − F} or table filling on n(n−1)/2 pairs. x ≡L y ⇔ ∀z (xz ∈ L ⇔ yz ∈ L). L is regular ⇔ index of ≡L is finite, and index = number of states in the unique minimal DFA.
- Mealy vs Moore: Moore λ : Q → Δ outputs n + 1 symbols for length-n input; Mealy λ : Q × Σ → Δ outputs n symbols. Moore → Mealy: same states; Mealy → Moore: ≤ |Q|·|Δ| states.
- Precedence & identities: * > concatenation > +. ∅ + r = r; ∅r = r∅ = ∅; εr = r; ∅* = ε* = ε; (r*)* = r*; r*r* = r*; ε + rr* = r*; (rs)*r = r(sr)*; (r + s)* = (r*s*)* = (r* + s*)* = r*(sr*)* = (r*s)*r*.
- Conversions: Strict Thompson ε-NFA adds 2 states per symbol, union, and star. State elimination bypass: R(p,q) ← R₄ + R₁R₂*R₃. Arden’s theorem: R = Q + RP has unique solution R = QP* when ε ∉ L(P).
- Regular grammars: Right-linear (A → wB | w) or left-linear (A → Bw | w). Mixing right- and left-linear rules gives linear grammars (can generate anbn, not guaranteed regular).
- Algorithms (n-state DFA): Emptiness: is F reachable? (iff some w of length < n accepted). Finiteness: cycle on useful path (iff some w with n ≤ |w| < 2n accepted). Equivalence: minimize both or test (L₁ ⊕ L₂) = ∅.
- CFG & ambiguity: A → α (A ∈ V). Parse trees ↔ leftmost derivations ↔ rightmost derivations (1-to-1). Ambiguous CFG = some w has ≥ 2 parse trees. Inherently ambiguous CFL: {aibjck : i = j or j = k}.
- Cleanup & normal forms: Clean in order: ε-productions → unit productions → useless symbols (non-generating first, then unreachable). CNF: A → BC | a (and S → ε if S not on RHS); deriving |w| = n ≥ 1 takes 2n − 1 steps (n − 1 binary splits + n terminal rules); binary parse tree height h gives |w| ≤ 2h (or 2h−1 counting terminal edges). GNF: A → aα (α ∈ V*); deriving |w| = n takes n steps.
- PDA & DCFL vs CFL: NPDA (final state) ≡ NPDA (empty stack) ≡ CFG. DPDA (empty stack) accepts only prefix-free DCFLs; DPDA (final state) accepts all DCFLs. Regular ⊊ DCFL ⊊ CFL. Every DCFL has an unambiguous grammar, and is closed under complement.
- Turing machine & variants: M = (Q, Σ, Γ, δ, q₀, □, qacc, qrej). Multi-tape, multi-head, 2D-tape, stay-option, semi-infinite tape, offline, and nondeterministic TMs, plus 2-stack PDAs and 2-counter machines, all have the exact same power as a standard deterministic TM.
- Chomsky hierarchy: Type 3 (Regular, DFA/NFA) ⊊ DCFL (DPDA) ⊊ Type 2 (CFL, NPDA) ⊊ Type 1 (CSL, LBA, non-contracting α → β with |α| ≤ |β|) ⊊ REC (Decidable, halting TM) ⊊ Type 0 (RE, unrestricted grammar / TM).
- REC vs RE: L ∈ REC (decidable) iff a TM halts on all inputs. L ∈ RE (Turing-recognizable) iff a TM halts and accepts on w ∈ L (may loop on w ∉ L). Complementation theorem: L is decidable (REC) ⇔ both L and L̅ are RE (i.e. L ∈ RE ∩ co-RE).
- Countability: Σ* and the set of all TMs (hence all RE languages) are countably infinite (ℵ₀). The set of all languages P(Σ*) is uncountable (2ℵ₀) — so most languages are not even RE.
- Key undecidable languages: Ld (not RE); ATM, HALTTM, E̅TM = {⟨M⟩ : L(M) ≠ ∅} (RE but not REC); A̅TM, ETM = {⟨M⟩ : L(M) = ∅} (co-RE, not RE); EQTM, TOTALTM = {⟨M⟩ : M halts on all inputs}, ALLTM = {⟨M⟩ : L(M) = Σ*}, REGTM, CFLTM (neither RE nor co-RE).
- Mapping reduction A ≤m B: computable total f with w ∈ A ⇔ f(w) ∈ B. B decidable ⇒ A decidable; A undecidable ⇒ B undecidable; B ∈ RE ⇒ A ∈ RE; A ∉ RE ⇒ B ∉ RE. To prove B undecidable, reduce a known undecidable A to B (A ≤m B).
- Rice’s theorem: Every non-trivial semantic property of RE languages (depends only on L(M), neither ∅ nor all RE languages) is undecidable. Syntactic properties of M’s code/states or bounded-step runs are decidable!
- PCP: Post Correspondence Problem is undecidable over |Σ| ≥ 2 (RE-complete), decidable over a unary alphabet |Σ| = 1.
2Master Closure Properties Table
Memorize the columns: Regular is ✓ everywhere; DCFL keeps only complement, ∩R, /R, h⁻¹; CFL fails ∩, complement, difference; CSL and REC are ✓ except arbitrary (ε-erasing) homomorphism and quotient (every RE language is a quotient of a decidable one by a regular set); RE fails only complement and difference.
| Operation | Regular | DCFL | CFL | CSL | REC (Decidable) | RE |
|---|---|---|---|---|---|---|
| Union (L₁ ∪ L₂) | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Intersection (L₁ ∩ L₂) | ✓ | ✗ | ✗ | ✓ | ✓ | ✓ |
| Complement (L̅) | ✓ | ✓ | ✗ | ✓ | ✓ | ✗ |
| Set difference (L₁ − L₂) | ✓ | ✗ | ✗ | ✓ | ✓ | ✗ |
| Concatenation (L₁L₂) | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Kleene star (L*) | ✓ | ✗ | ✓ | ✓* | ✓ | ✓ |
| Reversal (Lᴿ) | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Homomorphism h(L) | ✓ | ✗ | ✓ | ✗ | ✗ | ✓ |
| ε-free homomorphism | ✓ | ✗ | ✓ | ✓ | ✓ | ✓ |
| Inverse homomorphism h⁻¹(L) | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| Intersection with regular (L ∩ R) | ✓ | ✓ | ✓ | ✓ | ✓ | ✓ |
| Quotient with regular (L / R) | ✓ | ✓ | ✓ | ✗ | ✗ | ✓ |
3Master Decidability Table
Rows are decision problems given a machine or grammar from the class; columns are language classes. Notice the sharp cliff from Regular to CFL to CSL/REC/RE.
| Problem | Regular | DCFL | CFL | CSL (LBA) | REC | RE (TM) |
|---|---|---|---|---|---|---|
| Membership (w ∈ L?) | Decidable | Decidable | Decidable (CYK) | Decidable | Decidable | Undecidable |
| Emptiness (L = ∅?) | Decidable | Decidable | Decidable | Undecidable | Undecidable | Undecidable |
| Finiteness (|L| < ∞?) | Decidable | Decidable | Decidable | Undecidable | Undecidable | Undecidable |
| Equivalence (L₁ = L₂?) | Decidable | Decidable* | Undecidable | Undecidable | Undecidable | Undecidable |
| Universality (L = Σ*?) | Decidable | Decidable | Undecidable | Undecidable | Undecidable | Undecidable |
| Inclusion (L₁ ⊆ L₂?) | Decidable | Undecidable | Undecidable | Undecidable | Undecidable | Undecidable |
| Regularity (is L regular?) | Decidable (trivial) | Decidable | Undecidable | Undecidable | Undecidable | Undecidable |
| Ambiguity of grammar | Decidable | — (unambiguous) | Undecidable | Undecidable | — | — |
4Minimal-DFA State-Count Formulas & Normal-Form Bounds
| Language / Construction (over alphabet Σ, |Σ| = m ≥ 2) | Minimal DFA States / Formula | Key Trap / Note |
|---|---|---|
| Single string {w} of length k | k + 2 | k + 1 progress states + 1 dead state |
| Starts with w (|w| = k) | k + 2 | Needs dead state for wrong prefix |
| Ends with w (|w| = k) | k + 1 | No dead state; KMP-style fallback edges |
| Contains w as substring (|w| = k) | k + 1 | State k is an accepting sink; no dead state |
| Length |w| = k (or |w| ≤ k) | k + 2 | Lengths 0..k plus dead state for > k |
| Length |w| ≥ k | k + 1 | Lengths 0..k−1 plus accepting sink ≥ k |
| Length |w| ≡ r (mod n) | n | Cycle of n remainder states 0..n−1 |
| #a = k (or #a ≤ k) | k + 2 | Counts 0..k plus dead state for > k |
| #a ≥ k | k + 1 | Counts 0..k−1 plus accepting sink ≥ k |
| #a ≡ r₁ (mod m) AND/OR #b ≡ r₂ (mod n) | m · n | Grid of remainders (when conditions are non-trivial) |
| k-th symbol from START is a | k + 2 | k − 1 skip states + accept sink + dead state |
| k-th symbol from END is a | 2k | NFA has k + 1 states; DFA tracks all length-k suffixes |
| Binary number divisible by k (odd k) | k | If k = 2r · m (m odd), minimal states = m + r (or max(r+1, …) if 0 handled) |
| Strings of length n with no "aa" over {a,b} | Fn+2 strings (3-state DFA) | For n = 0,1,2,3,4,5: 1, 2, 3, 5, 8, 13 |
| Subset construction on n-state NFA | ≤ 2n states | Count only reachable subsets; include ∅ if reached |
| CNF derivation of w (|w| = n ≥ 1) | 2n − 1 steps | n − 1 binary steps (A → BC) + n terminal steps (A → a) |
| GNF derivation of w (|w| = n ≥ 1) | n steps | Each rule A → aα emits exactly 1 terminal |
5Pumping Lemmas & Standard Witness Languages
Regular Pumping Lemma (2.4.3)
If L is regular, ∃p ≥ 1 such that ∀w ∈ L with |w| ≥ p, ∃ split w = xyz:
1. |xy| ≤ p (pump occurs in first p symbols)
2. |y| ≥ 1
3. ∀i ≥ 0, xyiz ∈ L.
Contrapositive use only: failing proves non-regular; passing proves nothing.
1. |xy| ≤ p (pump occurs in first p symbols)
2. |y| ≥ 1
3. ∀i ≥ 0, xyiz ∈ L.
Contrapositive use only: failing proves non-regular; passing proves nothing.
CFL Pumping Lemma (3.4.3)
If L is a CFL, ∃p ≥ 1 such that ∀z ∈ L with |z| ≥ p, ∃ split z = uvwxy:
1. |vwx| ≤ p (short window anywhere)
2. |vx| ≥ 1 (at least one of v, x non-empty)
3. ∀i ≥ 0, uviwxiy ∈ L.
Key idea: vwx cannot span 3 blocks of length p in apbpcp.
1. |vwx| ≤ p (short window anywhere)
2. |vx| ≥ 1 (at least one of v, x non-empty)
3. ∀i ≥ 0, uviwxiy ∈ L.
Key idea: vwx cannot span 3 blocks of length p in apbpcp.
| Smallest Class | Canonical Witness Languages | Why it lives here (and not one shell inward) |
|---|---|---|
| Regular | a*b*, {w : #a ≡ #b mod k}, {wxwR : w,x ∈ Σ+}, {w : #ab = #ba}, {ww : w ∈ a*}, any finite language | Needs only bounded memory (remainders, last k symbols, or x absorbs middle) |
| DCFL (not Regular) | {anbn}, {wcwR}, balanced parentheses, {w : #a = #b}, {aibj : i ≠ j}, {anbmcn}, {anbncmdm} | Needs 1 unbounded stack, and transition from push to pop is deterministic |
| CFL (not DCFL) | {wwR}, palindromes without centre marker, {anbn} ∪ {anb2n}, {aibjck : i = j or j = k}, Σ* − {ww} | 1 stack suffices, but machine must nondeterministically guess the midpoint or which condition holds |
| CSL (not CFL) | {anbncn}, {ww : w ∈ {a,b}*}, {anbmcndm}, {w : #a = #b = #c}, {an²}, {a2ⁿ}, {ap : p prime} | Needs ≥ 2 independent comparisons or crossing matches; LBA decides in linear space |
| REC (Decidable, not CSL) | Languages decidable only with super-linear space, or diagonalization over LBAs | Halting TM exists, but linear tape bound is exceeded |
| RE (not REC) | ATM = {⟨M,w⟩ : M accepts w}, HALTTM, {⟨M⟩ : L(M) ≠ ∅}, PCP instances with a match | TM can confirm "yes" by simulating/searching, but loops forever on "no" |
| Not RE (co-RE or neither) | Ld (diagonal), A̅TM, ETM = {⟨M⟩ : L(M) = ∅} (co-RE); EQTM, TOTALTM, ALLTM (neither RE nor co-RE) | No TM can even recognize "yes" instances (would require checking infinitely many runs or halting) |