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*).

Theory of Computation

4 topics · 118 Qs · 6.9 marks/paper · since 2011

Start mock (30 Qs)

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'… Guide

Topics

Open a topic to browse, or practice it timed.

By year

Jump to the first question from that paper.

Subject guide

What does GATE test in Theory of Computation?

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)

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*).

How questions show up

Minimal DFA State Counting for Modulo / Arithmetic / Group Constraints
common · NAT · 2 marks · 2025, 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
common · mixed · 1 marks · 2023, 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
common · MCQ · 2 marks · 2024, 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
common · MSQ · 1 marks · 2026, 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
occasional · mixed · 2 marks · 2024, 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
occasional · mixed · 2 marks · 2024, 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.