What are common examiner traps in Regular Expressions and Finite Automata?

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*). Confusing 'length less than or equal to n' with 'length exactly equal to n'.

GATE CSE Regular Expressions and Finite Automata PYQs

Medium yield33.9% of 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. Questions test minimal DFA state… Read the guide

Take topic test

Questions: 41
Asked: since 2011
Total marks: 61
Marks / paper: 2.3

41 GATE CSE Regular Expressions and Finite Automata PYQs with solutions, from Theory of Computation. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Regular Expressions and Finite Automata

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. Questions test minimal DFA state counting under modulo/substring constraints, state equivalence and minimization, regular expression derivation from transition graphs (and vice versa), NFA-to-DFA powerset bounds ( $2^n$ ), and language membership/closure properties. The distribution balances 1-mark foundational conceptual checks with 2-mark state-tracing and counting problems.

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

Recurring question patterns

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.
Language Regularity and Language Operations (Complementation / Intersection)
OccasionalMCQ2 marks2026, 2021, 2015, 2014
Evaluating whether languages with count differences, alternating sub-blocks, or intersections are regular, or finding the minimal DFA size after complementation/intersection.
Bounded-Length Complement/Union String Counting
CommonNAT2 marks2024
Given two or more regular expressions over an alphabet $\Sigma$ , compute the total number of strings of length up to a bound $n$ that belong to neither expression (or belong to their intersection/union).

Formulas GATE uses

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.

Examiner traps in Regular Expressions and Finite Automata

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*).
Confusing 'length less than or equal to n' with 'length exactly equal to n'.

How questions are asked

Compute minimal number of DFA states for a given language description (NAT)
Match a given state transition graph to the correct regular expression (MCQ)
Multi-statement verification on state distinguishability and regex identities (MSQ)
Compute extended transition function (q, w) on an -NFA (MCQ)
Count the number of accepted strings of a fixed length k (NAT)
Identify which strings belong to the Kleene star closure L* of a finite language (MCQ)
bounded-length string enumeration and counting under regex constraints

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

Difficulty notes

Easy items test standard definitions (e.g., powerset bound $2^n$ , single loop regexes, direct path tracing on small NFAs). Medium items involve finding minimal DFA state counts under multi-step modulo or substring constraints, computing state distinguishability pairs, and identifying algebraic regex identities via MSQ. Hard items involve proving regularity of subtle unbounded-difference vs bounded-difference counting languages (e.g., alternating subpatterns) or analyzing interlocking cycles in multi-automata intersections.