What are common examiner traps in Theory of Computation?

Forgetting the trap/dead state when counting minimal DFA states for prefix/pattern-avoidance constraints. Assuming empty string is always in L(M) when start state is non-accepting (e.g., k>0 vs k ≥ 0). Confusing 'contains substring w' (requires trap on success) with 'ends with substring w' (resets based on longest suffix overlap). Assuming all-accepting states in an NFA implies accepting * (ignoring missing transitions / dead branches). Believing minimal DFA for an n-state NFA must have ≥ n states (it can be 1 state if L = *). Incorrectly applying complementation to an incomplete DFA without first adding explicit transitions to a dead state. Forgetting the empty string (length 0) when calculating total strings Σk=0n | |k or evaluating 0* + 1*. Double-counting overlap strings between expressions (e.g., length-1 strings '0' and '1' generated by both 0*+1* and 01*+10*).

GATE CSE Theory of Computation (TOC) PYQs

The topic of Regular Expressions and Finite Automata is one of the highest-weight core areas in GATE CS Theory of Computation. Across GATE CS, 'Turing machines… Read the guide

Start mock · 30 Qs

Topics: 4
Questions: 118
Marks / paper: 6.9
Asked: since 2011

These are the 118 GATE CSE Theory of Computation PYQs (since 2011), grouped topic-wise with solutions. See all GATE CSE PYQs or GATE CSE question papers by year.

Topics

Open a topic to browse its questions, or practice it as a timed test.

By year

Jump to the first question from each year’s paper.

What GATE tests in Theory of Computation

Concepts, patterns, formulas and traps distilled from past papers.

The topic of Regular Expressions and Finite Automata is one of the highest-weight core areas in GATE CS Theory of Computation. Across GATE CS, 'Turing machines and undecidability' is consistently tested through theoretical properties of computability and complexity classes. Context-Free Grammars (CFG) and Pushdown Automata (PDA) form a cornerstone of the GATE CS Theory of Computation syllabus.

Core concepts

Deterministic and Non-Deterministic Finite Automata (DFA, NFA, -NFA)
Myhill-Nerode theorem and state distinguishability
DFA state minimization (table-filling algorithm and dead state merging)
Extended transition function and -closure computation
Conversion between regular expressions and finite automata (Arden's theorem / state elimination)
Complementation, intersection, and product automata constructions
Finite state tracking for modular arithmetic and group actions
Language generated by regular expressions (+, ·, *, and )
Length-wise string enumeration
Intersection and disjointness of regular languages
Complement language cardinality over finite length bounds
Rice's Theorem (semantic/non-trivial properties of RE languages vs syntactic/step-bounded properties)

How questions show up

Minimal DFA State Counting for Modulo / Arithmetic / Group Constraints
CommonNAT2 marks2025, 2020, 2011
Given a language condition based on symbol counts modulo $m$ , divisibility by multiple numbers (LCM), or algebraic properties (e.g., product modulo 7), find the exact number of states in the minimal DFA.
Minimal DFA State Counting for Suffix / Substring / Exact Position Constraints
Commonmixed1 marks2023, 2021, 2017, 2016
Determining the minimal number of states for accepting strings containing, ending in, or avoiding specific substrings (e.g., $k$ -th symbol from right, avoiding $111$ , exact length plus symbol conditions).
Automaton to Regular Expression Equivalence / Loop Identification
CommonMCQ2 marks2024, 2023, 2022, 2021
Given a transition diagram of a DFA, NFA, or $\epsilon$ -NFA, identify the equivalent regular expression by decomposing cycles, state elimination, or tracking paths to multiple accept states.
NFA to DFA Conversion and Powerset State Bounds
CommonMSQ1 marks2026, 2025, 2018, 2016
Testing theoretical bounds on state counts when converting an $n$ -state NFA to a DFA ( $k \le 2^n$ ), minimal equivalent DFAs, and behavior of all-accepting NFAs.
State Distinguishability, Equivalence, and Minimization
Occasionalmixed2 marks2024, 2017, 2014, 2011
Given an automaton transition table or diagram, compute reachable state sets, $\epsilon$ -closures, identify equivalent/trap states, or find distinguishable state pairs.
String Membership, Decomposition, and Finite Length Counting
Occasionalmixed2 marks2024, 2021, 2014, 2012
Checking whether given candidate strings belong to $L^*$ , finding the shortest string not generated by a regex, or counting accepted strings up to a fixed length.

High-yield formulas

Subset Construction Maximum State Bound

|Q_{DFA}| \le 2^{|Q_{NFA}|}

Determining maximum possible states in an equivalent DFA converted from an NFA.

k-th Symbol from Right State Requirement

|Q_{min}| = 2^k \quad \text{for alphabet } |\Sigma| = 2

Finding minimal DFA states for languages tracking the $k$ -th symbol from the end of a binary string.

DFA Complementation Invariance

\text{States}(M_{\overline{L}}) = \text{States}(M_L) \quad \text{for minimal complete DFA } M_L

Determining state count of complement DFA by inverting final and non-final states.

Divisibility Modulo Intersection / LCM Rule

\text{States} = \operatorname{lcm}(m, n)

Tracking independent modular conditions on symbol counts (e.g. divisible by $m$ but not by $n$ ).

Regular Expression Star Identity

(r^* s^*)^* = (r + s)^*

Simplifying and matching equivalent regular expressions from state transition cycles.

Total Strings of Length up to $n$ over Alphabet $\Sigma$

N_{\le n} = \sum_{k=0}^{n} |\Sigma|^k = \frac{|\Sigma|^{n+1}-1}{|\Sigma|-1}

Used to find the size of the universal set of strings of length $\le n$ before subtracting strings accepted by given regular expressions.

Principle of Inclusion-Exclusion for String Counts

|L(r) \cup L(s)|_{\le n} = |L(r)|_{\le n} + |L(s)|_{\le n} - |L(r) \cap L(s)|_{\le n}

Used when determining the union of languages defined by multiple regular expressions without double-counting shared strings.

Post's Theorem

L \in \text{REC} \iff (L \in \text{RE}) \land (\overline{L} \in \text{RE})

Used when analyzing the decidability of $L$ given the enumerability of $L$ and $\overline{L}$ .

Examiner traps in Theory of Computation

Forgetting the trap/dead state when counting minimal DFA states for prefix/pattern-avoidance constraints.
Assuming empty string is always in L(M) when start state is non-accepting (e.g., k>0 vs k ≥ 0).
Confusing 'contains substring w' (requires trap on success) with 'ends with substring w' (resets based on longest suffix overlap).
Assuming all-accepting states in an NFA implies accepting * (ignoring missing transitions / dead branches).
Believing minimal DFA for an n-state NFA must have ≥ n states (it can be 1 state if L = *).
Incorrectly applying complementation to an incomplete DFA without first adding explicit transitions to a dead state.
Forgetting the empty string (length 0) when calculating total strings Σk=0n | |k or evaluating 0* + 1*.
Double-counting overlap strings between expressions (e.g., length-1 strings '0' and '1' generated by both 0*+1* and 01*+10*).

Paper trends

Introduction of MSQ format has shifted subset construction and state-equivalence questions into multi-correct evaluations testing extreme cases (e.g., minimal DFA bounds $\le 2^n$ , state distinguishability pairs).
2026, 2025, 2024, 2021
Transition from purely visual DFA/regex matching to algebraic modulo operations, multiplicative group residue tracking, and finite string counting via combinatorics.
2025, 2024, 2021, 2020
Persistent use of NAT for state counting problems where students must avoid off-by-one errors regarding start states and dead/trap states.
2025, 2024, 2023, 2021, 2020, 2017, 2016, 2015, 2014
Recent questions test regex understanding via numerical answer type (NAT) combinatorial string counting rather than traditional DFA equivalence or property matching.
2024