Short notes: Theory of Computation
Every topic in revision form: the key ideas, formulas, the question types GATE asks, and the traps. Read it the night before.
The most predictable TOC marks: count states of a minimal DFA, read the language of a given automaton, convert NFA to DFA.
- DFA: the machine with no choices. A DFA is (Q, Σ, δ, q₀, F). From every state there is exactly one move on every symbol. Its only memory is the current state, so it can never count without a bound. A string is accepted if it ends in a final state.→ DFA = one move per state and symbol; memory is only the current state.
- NFA and ε-NFA. An NFA may have several or no moves on a symbol, and an ε-NFA may also move without reading. A string is accepted if some path ends in a final state. NFAs are easier to design but recognise exactly the same languages as DFAs: the regular languages.→ NFA = guess and accept if any path works; same power as a DFA.
- NFA → DFA: subset construction. Each DFA state is a set of NFA states. Start from the ε-closure of the start state; for each symbol take move(set, a) and then its ε-closure; a DFA state is final if it contains an NFA final state. n NFA states can give up to 2n DFA states.→ DFA states are subsets of NFA states; at most 2ⁿ.
- DFA minimisation and Myhill–Nerode. Two states are equivalent if no string leads one to a final state and the other to a non-final state. Delete unreachable states, then merge equivalent ones (partition refinement). The minimal DFA is unique, and its state count equals the number of Myhill–Nerode classes.→ Minimal DFA: remove unreachable, then merge indistinguishable states.
- Designing DFAs and counting states. Think of what the machine must remember: the last few symbols (ends with / contains), a remainder (divisibility), or parity. Union and intersection of two DFAs use the product construction (m × n states). Complement = swap final and non-final in a complete DFA.→ Pattern of length m: m + 1 states; mod k: k states; AND/OR: multiply.
Formulas
What GATE asks
- ★★★Minimum number of states in a DFA for a language. Ends with / contains / divisible by / starts with. Decide whether a dead state is counted (complete DFA).
- ★★★What language does this automaton accept?. Given a DFA/NFA figure, pick the regex, the verbal description, or a string that is accepted.
- ★★★NFA → DFA state count. Run the subset construction on a small NFA and count reachable subsets.
- ★★★Equivalence of DFA states / closure statements. Which states merge in the minimal DFA; true/false on NFA vs DFA power.
Traps
Closure-property statements, regex identities and "is this language regular?" (pumping lemma) appear almost every year.
- Regular expressions and identities. Regexes are built from ∅, ε, symbols, union (+), concatenation and star. Useful identities: R + R = R, (R*)* = R*, ε + RR* = R*, (R + S)* = (R*S*)* = (R* + S*)*, R(SR)* = (RS)*R, ∅* = ε, R∅ = ∅.→ To refute equality, find one string in one language and not the other.
- Regex ⇄ finite automaton. Regex → ε-NFA by Thompson's construction (≤ 2 states per symbol/operator). DFA → regex by state elimination, or by Arden's theorem: if R = Q + RP and ε ∉ P, then R = QP*. All three formalisms describe exactly the regular languages.→ Regex ⇔ NFA ⇔ DFA; Arden: R = QP*.
- Closure and decision properties. Regular languages are closed under union, intersection, complement, difference, concatenation, star, reversal, homomorphism, inverse homomorphism, quotient and prefix. Decidable: membership, emptiness, finiteness, equivalence, containment, universality.→ Regular is closed under almost everything; infinite union is the exception.
- Pumping lemma for regular languages. If L is regular there is a p such that every s ∈ L with |s| ≥ p can be split s = xyz with |xy| ≤ p, |y| ≥ 1 and xyⁱz ∈ L for all i ≥ 0. Use it as a game to prove a language is not regular. It can never prove a language regular.→ Pumping lemma: beat every split to prove non-regular. It never proves regular.
- Recognising non-regular languages. A language needs unbounded memory if it compares or counts: aⁿbⁿ, ww, palindromes, aⁿ² , primes, equal numbers of a and b. By Myhill–Nerode, L is regular iff it has finitely many equivalence classes. Every finite language is regular; a subset of a regular language need not be.→ If it must remember an unbounded number, it is not regular.
Formulas
What GATE asks
- ★★★Is this language regular / context-free?. Classify languages such as aⁿbⁿ, ww, aⁿbᵐ with conditions, using the pumping lemma or closure.
- ★★★Closure-property true/false statements. Union, intersection, complement, reversal, infinite union, subsets of regular languages.
- ★★★Which regular expression matches the language/DFA?. Test candidate regexes on short strings; spot equivalent ones using identities.
- ★★★Minimal states / equivalence. Number of states in the minimal DFA of a regex-defined language.
Traps
Ambiguity, normal forms, closure of CFLs and "is it a CFL?" questions are among the most repeated.
- CFG, derivations and parse trees. G = (V, Σ, P, S) with rules A → α. A derivation rewrites S step by step; leftmost / rightmost always expands the leftmost / rightmost variable. Each parse tree corresponds to exactly one leftmost derivation.→ Derivation order does not change the parse tree; ambiguity counts trees.
- Ambiguity. A grammar is ambiguous if some string has two parse trees (two leftmost derivations). A language is inherently ambiguous if every grammar for it is ambiguous (e.g. {aⁱbʲcᵏ : i = j or j = k}). Deciding whether a CFG is ambiguous is undecidable.→ Two parse trees for one string = ambiguous. Layering fixes precedence.
- Simplification and normal forms. Remove ε-productions, then unit productions, then useless symbols. CNF: every rule is A → BC or A → a (a string of length n takes exactly 2n − 1 steps). GNF: every rule is A → aα (n steps for length n).→ CNF: length n ⇒ 2n − 1 steps. GNF: n steps.
- CFL closure and the pumping lemma. CFLs are closed under union, concatenation, star, reversal, homomorphism and intersection with a regular language. They are not closed under intersection or complement. Pumping lemma: s = uvwxy with |vwx| ≤ p, |vx| ≥ 1, uvⁱwxⁱy ∈ L. Proves aⁿbⁿcⁿ, ww and aⁿ² are not CFLs.→ CFL: ∪ · * reverse yes; ∩ and complement no.
- Membership and decision problems for CFLs. CYK decides membership in O(n³) time using a CNF grammar. Emptiness and finiteness are decidable. Equivalence, universality (L(G) = Σ*) and "is the intersection empty" are undecidable.→ CYK = CNF + triangular table, O(n³).
Formulas
What GATE asks
- ★★★Is the grammar ambiguous? / which grammar is unambiguous. Find two parse trees for a string, or check precedence/associativity rules.
- ★★★Which languages are context-free. Apply the pumping lemma / closure: aⁿbⁿcⁿ, ww, equal counts, aⁿbᵐcᵏ with conditions.
- ★★★CFL closure true/false. Intersection with regular, complement, union, difference.
- ★★★Normal forms / simplification. Number of productions or derivation steps in CNF/GNF; remove ε and unit rules.
- ★★★Language generated by a grammar. Read the language off a grammar (and what it does NOT generate).
Traps
Design a PDA, decide deterministic vs nondeterministic, and relate PDAs to CFGs.
- The PDA and how it accepts. A PDA is an NFA plus a stack: δ(q, input or ε, stack top) gives (new state, string to push). It accepts by final state or by empty stack; for nondeterministic PDAs the two modes are equivalent in power.→ PDA = NFA + stack; accept by final state or empty stack.
- PDA ⇔ CFG. A language is context-free iff some NPDA accepts it. From a CFG: a PDA with one state that, with a variable on top, replaces it by the right side of a rule, and with a terminal on top, matches it with the input.→ CFG → PDA: expand variables on the stack, match terminals with input.
- Deterministic vs nondeterministic PDAs. DCFL ⊊ CFL. aⁿbⁿ and wcwᴿ are deterministic; wwᴿ (palindromes) needs nondeterminism to guess the middle. DCFLs are closed under complement but not under union, intersection or reversal. Every DCFL has an unambiguous grammar.→ DPDA ⊊ NPDA. Palindromes need nondeterminism.
- Designing PDAs and counting. Push a marker per symbol of the first block and pop one per symbol of the second (aⁿbⁿ). For aⁿb²ⁿ push two per a. One stack can compare one pair of counts, which is why aⁿbⁿcⁿ is out of reach. A PDA with two stacks is as powerful as a Turing machine.→ One stack = one comparison.
Formulas
What GATE asks
- ★★★Which language is accepted by this PDA?. Read the transitions off a diagram or a figure; test short strings.
- ★★★DPDA vs NPDA. Is the language deterministic context-free? Palindromes vs aⁿbⁿ.
- ★★★Count accepted strings of a given length. Trace the PDA to count accepted strings of length n.
- ★★★Equivalence with CFG / closure. Statements about PDA acceptance modes and DCFL closure.
Traps
One table to rule them all: closure and decidability properties of every class, plus classifying a language.
- The Chomsky hierarchy. Type 3 regular ↔ finite automaton. Type 2 context-free ↔ PDA. Type 1 context-sensitive ↔ linear bounded automaton. Type 0 unrestricted ↔ Turing machine (RE). Each class properly contains the one before: Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE.→ Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE.
- Closure properties of each class. Regular: closed under everything common. CFL: no ∩, no complement. DCFL: complement yes, ∪ and ∩ no. CSL: closed under complement (Immerman–Szelepcsényi). Recursive: complement yes. RE: ∪ and ∩ yes, complement no.→ Complement: yes except CFL and RE.
- Decision properties of each class. For regular languages everything is decidable. For CFLs membership, emptiness and finiteness are decidable, but equivalence and universality are not. For TMs (recursive/RE) almost every interesting question is undecidable.→ CFL: membership, emptiness, finiteness yes; equivalence no.
- Classifying a language. Ask: does it need to count once (CFL), compare two things (CSL), or depend on halting behaviour (RE or worse)? aⁿbⁿ is DCFL; wwᴿ is CFL; aⁿbⁿcⁿ and ww are CSL but not CFL; the halting language is RE but not recursive.→ Count one thing: CFL. Count two things at once: not CFL.
Formulas
What GATE asks
- ★★★Statement about closure of a class. True/false on ∪, ∩, complement, concatenation for CFL, DCFL, recursive, RE.
- ★★★Which of these languages are CFL / regular / decidable. Classify 3–4 languages and pick the correct combination.
- ★★★Decidability of problems per class. Is emptiness / equivalence decidable for DFA, PDA, TM?
Traps
Recursive versus recursively enumerable, TM variants, and what a TM can do.
- The Turing machine model. A TM has an infinite tape, a read/write head and a finite control: δ(q, a) = (p, b, L/R). It accepts by entering the accept state, rejects by entering the reject state, or loops forever. A language is recognised if the TM accepts exactly its strings, and decided if the TM also always halts.→ TM: accept, reject or loop. Decider = always halts.
- Variants and equivalent models. Multi-tape, multi-track, two-way infinite tape, nondeterministic TMs and RAM machines all compute the same languages as the basic TM (only the speed differs: simulating k tapes costs a quadratic factor). A linear bounded automaton (tape = input) accepts exactly the context-sensitive languages.→ Variants change speed, not what is computable.
- Recursive versus recursively enumerable. Recursive (decidable): some TM halts on every input. RE (recognisable): some TM accepts the members but may loop otherwise. Recursive languages are closed under complement; RE languages are not. L and L̄ both RE ⇒ L is recursive.→ L and complement both RE ⇒ L recursive.
- Church–Turing thesis and TM design. Anything that is intuitively computable is computable by a TM. To design a TM: mark a symbol, scan to its partner, mark that, return to the start, repeat; accept when all are marked. The number of steps is usually Θ(n²) for such comparisons.→ Mark, scan, return, repeat.
Formulas
What GATE asks
- ★★★Recursive / RE / neither for a described language. Use closure rules and the "L and complement both RE" fact.
- ★★★Equivalence of TM variants. Which TM variants add no power.
- ★★★What does this TM compute / accept. Trace a small TM (e.g. aⁿbⁿ marker algorithm).
Traps
Halting problem, reductions and Rice's theorem: guaranteed conceptual questions.
- The halting problem. ATM = {⟨M, w⟩ : M accepts w} is RE but not recursive. The proof is by diagonalisation: a decider would let you build a machine D that does the opposite of every machine on its own description, which cannot be any machine. Its complement is not even RE.→ A_TM: RE and undecidable; its complement is not RE.
- Reductions. A ≤ B (many-one) means a computable f turns every instance of A into an instance of B. If B is decidable then A is decidable; contrapositive: if A is undecidable then B is undecidable. Also: B RE ⇒ A RE. The direction matters: reduce from a known undecidable problem to the new one.→ A ≤ B: B easy ⇒ A easy; A hard ⇒ B hard.
- Rice's theorem. Every non-trivial semantic property of L(M) is undecidable (e.g. L(M) = ∅, L(M) is regular, L(M) is finite, L(M) contains ε). It does not apply to trivial properties, to syntactic properties of M (number of states) or to properties of M's behaviour that are not about L(M) (e.g. "M halts within k steps").→ Rice: non-trivial semantic property of L(M) ⇒ undecidable.
- Standard decidable and undecidable problems. Decidable: emptiness/equivalence of DFAs, membership in a CFG, emptiness of a CFG, finiteness of a CFG, whether M halts within k steps. Undecidable: halting, emptiness/equality/regularity of a TM, CFG ambiguity, CFG equivalence and universality, whether L(G₁) ∩ L(G₂) is empty, Post's correspondence problem.→ DFA and CFG-emptiness: decidable. CFG-equality and anything on TMs: undecidable.
Formulas
What GATE asks
- ★★★Which problems are decidable?. Pick from lists about DFAs, CFGs and TMs; use Rice for TM-property questions.
- ★★★Apply reductions correctly. If L₁ ≤ L₂ and L₂ is decidable/RE, what follows for L₁? Direction traps.
- ★★★Recursive / RE classification. Is the language recursive, RE not recursive, or not RE?
- ★★★Rice's theorem applicability. Which properties does Rice cover, and which are decidable anyway?