TOC · GATE CS 2027
9 topics and 20 sheets. Open a topic for its sheets and the topics it depends on.
Operators and precedence, the identities that hold and the look-alikes that do not, writing an expression for a described language, equivalence checks with short counterexamples, counting strings of a given length, Thompson's regex to epsilon-NFA construction, epsilon-closure, state elimination and Arden's rule.
DFA, NFA and epsilon-NFA as tuples with acceptance, complete versus partial DFAs, the subset construction with its 2^n bound and tight witness, product construction for union, intersection and difference, minimisation by partition refinement and table filling, state counts for divisibility, substring, prefix, suffix and length conditions, and Moore and Mealy machines.
Closure of regular languages, decision procedures (membership, emptiness, finiteness, equivalence), Myhill-Nerode classes and the minimal DFA, the pumping lemma with the correct quantifier order and its common misuses, standard non-regular languages and fast classification of look-alikes.
Derivations, sentential forms, parse trees, leftmost and rightmost derivations, ambiguity and inherent ambiguity, grammar to language, removal of useless, epsilon and unit productions in the right order, Chomsky and Greibach normal forms with derivation lengths, and CYK membership.
PDA as a 7-tuple with instantaneous descriptions, acceptance by final state and by empty stack, PDAs for standard languages, NPDA versus DPDA, deterministic context-free languages and the prefix property, and the CFG to PDA and PDA to CFG constructions.
Closure of CFLs and DCFLs, including intersection with a regular language, decidable and undecidable questions for CFGs, the pumping lemma for CFLs with block arguments, closure proofs of non-context-freeness and the standard non-CFL languages.
Turing machine definition and configurations, a decider for a^n b^n, equivalent variants (multitape, nondeterministic, two-way, enumerators), recursive versus recursively enumerable languages, linear-bounded automata and CSLs, the Chomsky hierarchy and the closure master table.
Halting and acceptance problems, diagonalisation, mapping reductions and their direction, Rice's theorem and when it does not apply, Post correspondence, the decidability master table for regular, DCFL, CFL, CSL, recursive and RE languages, and complements of REC and RE.
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.
Regular expressions for GATE CS: the six building blocks, operator precedence, the identities that hold (with the empty set and epsilon cases) and the look-alikes that fail with their shortest counterexample, writing expressions for described languages such as no two consecutive a's or number of a's divisible by 3, testing two expressions for equivalence, and counting the strings of a given length. Every identity and construction was checked on all strings over {a, b} up to length 9.
Kleene's theorem in practice: Thompson's construction from a regular expression to an epsilon-NFA with its size bound and invariants, epsilon-closure and the removal of epsilon-moves without changing the state set, the state-elimination method from a DFA to an expression, and Arden's rule for solving language equations including the condition for a unique solution. Worked examples were built and compared with the target languages on all strings up to length 9.
The formal definitions of DFA, NFA and epsilon-NFA as 5-tuples, the extended transition function and acceptance, complete versus partial DFAs and the dead state, why swapping final states complements a complete DFA but not an NFA or a partial DFA, the equal power of the three models, and Moore and Mealy machines with output lengths and conversions. Every automaton shown was simulated on all strings up to length 10.
The subset construction from NFA or epsilon-NFA to DFA built on reachable subsets only, the empty set as the dead state, the 2^n upper bound and the k-th-symbol-from-the-end family that reaches it, the product construction for intersection, union, difference and symmetric difference with its m times n bound, examples where the product is not minimal, and the reversal blow-up. All subsets and state counts were computed by script.
Minimising a DFA: remove unreachable states, refine the final and non-final partition until stable (Moore), or mark distinguishable pairs round by round (table filling), with a fully worked six-state example including an unreachable state; the Myhill-Nerode relation and why the minimal DFA is unique up to renaming; class counts for standard languages; algorithm costs; complement and equivalence facts; and counting labelled DFAs. Every partition, mark and count is script output.
How to design DFAs by deciding what the machine must remember: remainder automata for divisibility in base 2 and other bases (with the m plus k rule for even divisors), substring, prefix and suffix automata, length and counting conditions, products of independent conditions, and counting the strings of length n that a DFA accepts by dynamic programming over states. Every minimal state count in the tables is computed by brute-force minimisation.
Closure of the regular languages under union, intersection, complement, difference, concatenation, star, reversal, homomorphism, inverse homomorphism and quotient, with the construction behind each; the decision procedures for membership, emptiness, finiteness, universality, equivalence and containment with their bounds; Myhill-Nerode as a characterisation; closure arguments that prove a language non-regular; and the one-way nature of closure (subsets, unions of non-regular languages, infinite unions). Decision bounds were tested on random DFAs.
The pumping lemma for regular languages with the exact quantifier order, the adversary-game method of using it, the choice of string that forces the pumped part into one block, the common misuses (choosing the split, ignoring the length condition, believing the converse), a non-regular language that still satisfies the lemma, and a classification table of regular and non-regular look-alikes. The pumping game and every classification claim were checked by script.
Context-free grammars as 4-tuples, derivations, sentential forms and yields, the one-to-one link between parse trees and leftmost derivations, ambiguous grammars and how to show ambiguity, standard ambiguous grammars and their unambiguous rewrites (precedence, associativity, dangling else), inherent ambiguity, the grammar-to-language table for standard grammars, and the solved 2026 question on counting derivations. Every language and parse-tree count was computed by script.
Grammar simplification for GATE CS: removing useless symbols (non-generating first, then unreachable, with the counterexample for the wrong order), epsilon-productions via nullable variables, and unit productions via unit pairs; Chomsky normal form and its conversion steps, Greibach normal form, exact derivation lengths (2n - 1 in CNF, n in GNF) and parse-tree shape; and the CYK membership algorithm with a full table for a small CNF grammar. Every transformed grammar was compared with the original on all strings up to length 9 or 10.
The push-down automaton as a 7-tuple, the move label convention, instantaneous descriptions and the turnstile, acceptance by final state and by empty stack and their equivalence for nondeterministic PDAs, and constructions for a^n b^n, a^n b^2n, ww^R (nondeterministic, with a diagram), wcw^R, equal numbers of a and b, balanced parentheses and a^i b^j c^k with i = j or j = k. Every PDA was simulated nondeterministically on all strings up to length 7 or 8 and compared with its language.
Deterministic PDAs and the deterministic context-free languages: the determinism condition, acceptance by final state versus empty stack and the prefix property, the proper inclusions regular in DCFL in CFL with witnesses, closure and decision facts that separate DCFLs from CFLs, unambiguity of DCFLs, the CFG to PDA construction (one state, expand on the stack) and the PDA to CFG triple construction with its variable count, and the solved 2025 question on what a DPDA accepts. The constructions were simulated on all strings up to length 8.
Closure of CFLs (union, concatenation, star, reversal, homomorphism, inverse homomorphism, intersection with a regular language) and the failures (intersection, complement, difference) with witnesses; decidable and undecidable questions for CFGs; the pumping lemma for CFLs with the vxy window argument and the strings to choose; closure proofs of non-context-freeness; Parikh's theorem for unary languages; and the standard non-CFL languages with the complement trap. Grammar and PDA claims were checked by script.
The Turing machine as a tuple with configurations, accept, reject and loop outcomes; a full decider for a^n b^n with its move table and step counts; equivalent variants (multitape, multitrack, two-way infinite tape, stay option, nondeterministic, two-stack PDA, enumerator) with the cost of simulation; recursive versus recursively enumerable languages, deciders versus recognisers and enumerators; linear-bounded automata and context-sensitive languages in brief; and countability. The decider was simulated on every string up to length 10.
The language hierarchy from finite through regular, DCFL, CFL, CSL, recursive and recursively enumerable to all languages, with the grammar type and machine for each and example languages in each ring; the closure master table for six classes under twelve operations; how to read the table (De Morgan consequences, the homomorphism exceptions); the solved 2023 and 2025 questions on closure; and a table of grammar types and machines. Table consistency and the past-question answers were checked by script.
Decision problems as languages of encodings, the acceptance and halting problems and why they are recognisable but undecidable, diagonalisation shown as a table, mapping reductions with their direction and what they transfer (decidability, recognisability), the standard reduction chain, Rice's theorem with its conditions and the cases it does not cover, its extension showing non-recognisability, the Post correspondence problem in brief, and the solved 2014 question on CFG decision problems.
The decidability master table for membership, emptiness, finiteness, universality, equivalence, containment, disjointness and regularity across regular, DCFL, CFL, CSL, recursive and RE languages, with the method behind each decidable entry; the four cases for a language and its complement; the standard problems with their exact status (RE, co-RE or neither); closure of REC and RE under complement and other operations; and the solved 2013 and 2018 questions. Table consistency and the past-question answers were checked by script.
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.
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 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.
