Theory of Computation Previous Year Questions
Analyzing previous year GATE questions in Theory of Computation reveals consistent patterns that you can use to target your preparation. This section focus...
PYQ Patterns in Automata and Regular Languages
Analyzing previous year GATE questions in Theory of Computation reveals consistent patterns that you can use to target your preparation. This section focuses on the automata and regular languages cluster, which has appeared in every GATE CS paper for more than a decade and consistently accounts for around three marks per year.
The most recurring question type asks for the number of states in the minimum DFA for a language defined by a regular expression or described in words. For example, GATE 2014 asked for the minimum number of states in a DFA that accepts all binary strings where the number of ones is divisible by 3 and the number of zeros is divisible by 2. The answer requires you to construct a DFA whose states track two counters simultaneously using a product construction, giving 3 times 2 equals 6 states. This type of question rewards students who understand product automata construction deeply.
Another recurring type presents an NFA or a transition table and asks which strings are accepted or which language is recognized. GATE 2016 presented a 4-state NFA and asked students to identify the language it accepted from four options. The right approach is to trace the computation for a few representative strings from each answer option and eliminate the wrong ones.
Questions on closure properties appear in roughly one out of three years. A typical framing: given that L1 is a regular language and L2 is a context-free language, which of the following is guaranteed to be regular? The answer usually involves intersection of two regular languages, or complement of a regular language, both of which preserve regularity.
The pumping lemma appears as a conceptual question rather than a proof exercise. GATE 2019 asked students to identify which of four given languages is regular. The trick is recognizing that one option had a constraint involving equal counts of two symbols, making it non-regular, while another had a constraint expressible by a DFA with a fixed number of states.
To prepare for this cluster, solve the GATE 2010 through 2024 questions on automata in one sitting, noting which techniques they require. You will find that DFA construction, minimization, product automata, and closure properties together cover about 80 percent of the questions. Focus your remaining time on those four techniques.
PYQ Patterns in Context-Free Languages and Grammars
Context-Free Languages and Grammars form the second major cluster of Theory of Computation previous year questions. These questions appear in most GATE papers and test a focused set of skills: identifying language class, designing or analyzing grammars, reasoning about ambiguity, and understanding PDA behavior.
A question type that has appeared multiple times asks you to determine whether a given grammar is ambiguous. GATE 2015 presented the grammar with start symbol S producing S plus S, S multiply S, a, and b, and asked whether it was ambiguous. The answer is yes because the string a plus b multiply a can be derived in two ways with different parse trees, reflecting different operator precedence interpretations. The technique is to find a short string and exhibit two distinct parse trees.
Another recurring type asks for the language generated by a given grammar. GATE 2017 presented a grammar and asked students to pick from four language descriptions. The right approach is to derive several strings of increasing length and identify the pattern. For grammars with recursive rules, the pattern often involves a repeated substructure that maps to a known language class.
Grammar transformation questions ask you to convert a grammar to Chomsky Normal Form or to remove a specific type of production. GATE 2013 asked which productions would remain after converting a given grammar to CNF. Practicing this transformation step by step, removing null productions first, then unit productions, then converting long rules, is the reliable approach.
Questions on intersections of language classes test closure properties. If GATE asks whether the intersection of two context-free languages is always context-free, the answer is no, as shown by the standard counterexample involving strings with equal counts of three symbols that can be decomposed into two context-free languages whose intersection is not context-free.
For PDA questions, GATE sometimes describes a PDA by its transitions and asks which language it accepts. The key is to trace what the stack does: if the PDA pushes a symbol for each a and pops for each b, it is likely accepting strings with equal a's and b's.
Practice these question types using GATE 2010 to 2024 papers. The grammar transformation and ambiguity questions are the most time-consuming, so practice them until you can complete each in four minutes or less.
PYQ Patterns in Decidability and Turing Machines
Decidability and Turing Machine questions in GATE are the most conceptual in Theory of Computation and are often high-value, appearing as two-mark questions. They test whether you understand the boundary between what is computable and what is not, and how reductions work.
A common GATE pattern presents four statements about decidability and asks which ones are true. GATE 2018 offered statements about whether the language of all TM descriptions that accept a finite language is decidable, and whether the language of all TM descriptions that reject all strings is recognizable. The tools needed are Rice's Theorem for the first and a closure argument for the second. These require precise reasoning, not computation.
Questions about the relationship between recursive and recursively enumerable languages appear frequently. GATE 2016 asked which of four language relationships correctly describes the hierarchy between these classes. Knowing that recursive languages form a proper subset of RE languages, and that the complement of an RE language need not be RE while the complement of a recursive language is always recursive, lets you answer these definitively.
Reduction questions ask you to show that one problem is at least as hard as another. GATE 2020 described a problem about program behavior and asked whether it was decidable. The right approach is to recognize that the problem concerns a non-trivial language property of a TM and apply Rice's Theorem to immediately conclude it is undecidable.
Complexity theory questions, which form the boundary between TOC and algorithms, ask about the classes P and NP, NP-completeness, and reductions. A problem is NP-complete if it is in NP and every NP problem reduces to it in polynomial time. GATE has asked students to identify which problems from a list are NP-complete and which reductions are valid.
A practical tip for PYQ preparation in this area: build a two-column table with decidable problems on one side and undecidable ones on the other. Include the recognizable-but-not-decidable problems as a third category. Reviewing this table the night before the exam is the single most efficient use of your last-minute TOC study time for this cluster.