Theory of Computation · topic
Pack-wide revision: the traps that cost marks with the correct rule, question patterns with a first step and a check, and a last-day master sheet of the highest-value facts, counts and tables.
The common mistakes across Theory of Computation, each as the wrong belief, the correct rule and a pointer to the sheet that explains it: regular-expression identities, dead states and complete DFAs, complementing NFAs, subset and product bounds, pumping lemma quantifiers, closure being one-way, ambiguity versus left recursion, derivation lengths in CNF, DPDA acceptance modes, CFL closure, Rice's theorem scope, reduction direction and the complement rule for RE.
A partial preview of the top of the sheet. The full sheet is in the Theory of Computation cheat sheet pack.
The recurring question shapes in Theory of Computation with a first step, a method, a check and the usual failure: minimum DFA states, NFA-to-DFA size options, counting accepted strings, regex equivalence, language classification, ambiguity and derivation counts, closure statements, decidability statements, Rice-type properties, REC and RE complements, PDA and DPDA questions, Moore and Mealy outputs and Arden's rule. Years seen are distinct exam years among the past questions verified for the v1 pack.
A partial preview of the top of the sheet. The full sheet is in the Theory of Computation cheat sheet pack.
A one-page summary of the whole Theory of Computation pack: the hierarchy with machines and grammar types, compact closure and decidability tables for regular, DCFL, CFL, REC and RE, minimal DFA state counts, the two pumping lemmas, classification at sight, regular expression and grammar facts, the key numbers (2^n, 2n - 1, n^(nk) 2^n) and the undecidability tools.
A partial preview of the top of the sheet. The full sheet is in the Theory of Computation cheat sheet pack.
