PYQ coming soon
EXAMhelp · GATE notes
Theory of Computation
CH 01Language classes at a glance
Key points
- Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE.
- Regular languages union, intersection, complement, concatenation, star — closed under all of them.
- CFLs are not closed under intersection or complement; CFL ∩ Regular = CFL.
- DCFLs are closed under complement, but not under union/intersection.
- Recursive languages are closed under complement; RE is not (L and L' both RE ⇒ L recursive).
Formulas & facts
- Regular
- DFA / NFA / regex
- CFL
- PDA / CFG
- Recursive
- Halting TM
- RE
- TM (accepts)
CH 02Decidability
Key points
- For regular languages, membership, emptiness, finiteness and equivalence are all decidable.
- For CFLs, membership, emptiness and finiteness are decidable; equivalence and ambiguity are undecidable.
- Rice's theorem: every non-trivial property of RE languages is undecidable.
- The halting problem is RE but not recursive.