Theory of Computation
Theory of Computation asks you to classify languages, construct automata, and reason about decidability. The exam rewards knowing exactly which closure property or pumping lemma applies, and which machine model corresponds to which language class.
Regular languages
- DFA, NFA and regular expressions are equally expressive; NFA to DFA is subset construction, up to 2ⁿ states.
- Regular languages are closed under union, intersection, complement, concatenation, star and reversal.
- Pumping lemma: if L is regular with pumping length p, every string of length ≥ p can be split xyz with |xy| ≤ p, |y| ≥ 1, and xyⁱz ∈ L for all i ≥ 0. It is necessary, not sufficient - use it only to prove non-regularity.
Context-free languages
- CFG ↔ nondeterministic PDA. DCFLs are a strict subset of CFLs.
- CFLs are closed under union, concatenation, star and homomorphism, but not under intersection or complement.
Decidability
- Emptiness and membership for regular languages and CFLs are decidable.
- The halting problem is undecidable and not co-recognisable; by Rice's theorem any non-trivial semantic property of recursively enumerable languages is undecidable.
Worked example
Show L = {aⁿbⁿ | n ≥ 0} is not regular. Suppose pumping length p; take s = aᵖbᵖ. Any split with |xy| ≤ p puts y entirely inside the a-block, so xy²z = a^(p+|y|)bᵖ, which is outside L. Contradiction. The language is nevertheless context-free: S → aSb | ε.
Traps that cost marks
- Concluding "not regular" implies "not context-free".
- Forgetting that every finite language is regular.
- Trying to complement an NFA without determinising it first.