Formula sheet
Every formula from every topic. Type to filter.
🔁 Finite Automata (DFA, NFA, ε-NFA)
Ends with a fixed string of length m
minimal DFA has m + 1 states
Contains a fixed substring of length m
minimal DFA has m + 1 states
Number of a's ≡ r (mod k)
k states (also: length ≡ r mod k)
Starts with a string of length m
m + 2 states (m + 1 plus one dead state)
m-th symbol from the end is a fixed symbol
2^m states in the minimal DFA (NFA needs only m + 1)
Product construction
|Q₁| × |Q₂| states for union or intersection
Subset construction bound
n NFA states → at most 2^n DFA states
Complement
swap F and Q − F (the DFA must be complete, i.e. have a dead state if needed)
🔤 Regular Expressions & Regular Languages
Arden's theorem
R = Q + RP, ε ∉ P ⇒ R = QP*
Star identities
(R*)* = R* · ε + RR* = R* · (R + S)* = (R*S*)*
Thompson size
ε-NFA has ≤ 2 × (#symbols + #operators) states
Closure of regular languages
∪ ∩ complement − · * reversal homomorphism inverse-homomorphism quotient: all closed
Pumping lemma
regular ⇒ ∃p ∀s (|s| ≥ p) ∃ xyz: |xy| ≤ p, |y| ≥ 1, ∀i ≥ 0 xyⁱz ∈ L
Myhill–Nerode
L regular ⇔ finite number of distinguishable classes (= states of the minimal DFA)
🌳 Context-Free Grammars & Languages
CNF derivation length
a string of length n needs exactly 2n − 1 derivation steps (2n − 1 internal nodes)
GNF derivation length
a string of length n needs exactly n steps
CYK
O(n³ · |G|) time, O(n²) table
CFL pumping lemma
s = uvwxy, |vwx| ≤ p, |vx| ≥ 1, ∀i ≥ 0: uvⁱwxⁱy ∈ L
CFL closure
closed: ∪ · * reverse homomorphism ∩regular. Not closed: ∩, complement, difference
Language of S → aSb | ab
{aⁿbⁿ : n ≥ 1}
🥞 Pushdown Automata
PDA definition
(Q, Σ, Γ, δ, q₀, Z₀, F)
Transition
δ(q, a, X) = {(p, γ)}: pop X, push γ, go to p
CFG → PDA
1 state, stack alphabet V ∪ Σ, accepts by empty stack
Power
NFA < DPDA < NPDA < (2-stack PDA = TM)
DCFL closure
closed under complement and intersection with regular; not under ∪, ∩, reversal, *
🧬 Language Hierarchy & Closure Tables
Inclusion chain
Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE ⊂ all languages
Machines
FA, DPDA, NPDA, LBA, TM (halting), TM
Key facts
L and L̄ both RE ⇒ L recursive; recursive closed under complement; RE not
🎞️ Turing Machines
TM definition
(Q, Σ, Γ, δ, q₀, B, F), δ: Q × Γ → Q × Γ × {L, R}
Recursive ⊂ RE
every recursive language is RE; not conversely
Complement rule
L, L̄ both RE ⇔ L recursive
Simulation cost
multi-tape TM → single-tape: O(t²); NTM → DTM: exponential
🚫 Decidability & Undecidability
A_TM
RE, undecidable; its complement is not RE
Reduction rules
A ≤ B and B decidable ⇒ A decidable; A ≤ B and A undecidable ⇒ B undecidable
Rice
non-trivial property P of L(M) ⇒ {⟨M⟩ : L(M) has P} undecidable
RE tests
L RE ⇔ some TM enumerates it ⇔ accepts it