1. Finite Automata
DFA: exactly one transition per symbol
NFA: zero/more transitions; ε-moves allowed
Theorem: DFA ≡ NFA (power-set construction)
Regular languages closed under ∪, ·, *, complement, intersection
Pumping lemma proves non-regularity
2. CFG & PDA
CFG: productions A → string of terminals/variables
Parse trees, ambiguity
PDA: NFA + stack; accepts CFLs
Chomsky hierarchy: Type-0 TM ⊃ Type-1 CSG ⊃ Type-2 CFG ⊃ Type-3 Regular
3. Turing Machines
TM = infinite tape + head + finite control
Accepts RE languages
Decidable (recursive) vs RE but undecidable
Classic undecidable: Halting problem, emptiness of TM language