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'.

Regular Expressions and Finite Automata

41 Qs · since 2011 · 61 marks · 2.3 marks/paperMedium yield

Take topic test

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

Type

GATE CSE 2026 Set 1Q26MSQ1 markEasyLet $M$ be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet. Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to $M$ ?
GATE CSE 2026 Set 2Q47MSQ2 marksHardDiagramConsider the following two finite automata $D_1$ and $D_2$ . Which of the following statements is/are true?
GATE CSE 2025 Set 1Q28MSQ1 markEasyA regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?
GATE CSE 2025 Set 1Q50MSQ2 marksMediumDiagramConsider the following deterministic finite automaton (DFA) defined over the alphabet, $\Sigma = \{a, b\}$ . Identify which of the following language(s) is/are accepted by the given DFA.
GATE CSE 2025 Set 2Q60NAT2 marksMediumLet $\Sigma = \{1,2,3,4\}$ . For $x \in \Sigma^*$ , let $prod(x)$ be the product of symbols in $x$ modulo 7. We take $prod(\epsilon) = 1$ , where $\epsilon$ is the null string. For example, $prod(124) = (1 \times 2 \times 4) \bmod 7 = 1$ . Define $L = \{x \in \Sigma^* \mid prod(x) = 2\}$ . The number of…
GATE CSE 2024 Set 1Q50MSQ2 marksMediumDiagramConsider the 5-state DFA $M$ accepting the language $L(M) \subset (0 + 1)^*$ shown below. For any string $w \in (0 + 1)^*$ let $n_0(w)$ be the number of 0's in $w$ and $n_1(w)$ be the number of 1's in $w$ . Which of the following statements is/are FALSE?
GATE CSE 2024 Set 1Q61NAT2 marksMediumConsider the following two regular expressions over the alphabet $\{0,1\}$ : $r = 0^* + 1^*$ $s = 01^* + 10^*$ The total number of strings of length less than or equal to 5, which are neither in $r$ nor in $s$ , is ________
GATE CSE 2024 Set 2Q22MCQ1 markEasyDiagramWhich one of the following regular expressions is equivalent to the language accepted by the DFA given below?
GATE CSE 2024 Set 2Q41MCQ2 marksMediumDiagramLet $M$ be the 5-state NFA with $\epsilon$ -transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $M$ ?
GATE CSE 2024 Set 2Q62NAT2 marksMediumLet $L_1$ be the language represented by the regular expression $b^*ab^*(ab^*ab^*)^*$ and $L_2 = \{ w \in (a + b)^* \mid |w| \le 4 \}$ , where $|w|$ denotes the length of string $w$ . The number of strings in $L_2$ which are also in $L_1$ is _________
GATE CSE 2023Q14MCQ1 markEasyDiagramConsider the Deterministic Finite-state Automaton (DFA) $\mathcal{A}$ shown below. The DFA runs on the alphabet $\{0, 1\}$ , and has the set of states $\{s, p, q, r\}$ , with $s$ being the start state and $p$ being the only final state. Which one of the following regular expressions correctly describes the…
GATE CSE 2023Q63NAT2 marksEasyConsider the language $L$ over the alphabet $\{0, 1\}$ , given below: $L = \{w \in \{0, 1\}^* \mid w \text{ does not contain three or more consecutive 1's}\}.$ The minimum number of states in a Deterministic Finite-State Automaton (DFA) for $L$ is __________.
GATE CSE 2022Q12MCQ1 markEasyDiagramWhich one of the following regular expressions correctly represents the language of the finite automaton given below?
GATE CSE 2021 Set 1Q38MCQ2 marksEasyConsider the following language. $L = \{w \in \{0, 1\}^* \mid w \text{ ends with the substring } 011\}$ Which one of the following deterministic finite automata accepts $L$ ?
GATE CSE 2021 Set 2Q9MCQ1 markMediumLet $L \subseteq \{0, 1\}^*$ be an arbitrary regular language accepted by a minimal DFA with $k$ states. Which one of the following languages must necessarily be accepted by a minimal DFA with $k$ states?
GATE CSE 2021 Set 2Q17NAT1 markEasyDiagramConsider the following deterministic finite automaton (DFA). The number of strings of length 8 accepted by the above automaton is ________.
GATE CSE 2021 Set 2Q47MSQ2 marksMediumWhich of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three.
GATE CSE 2020Q7MCQ1 markMediumWhich one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
GATE CSE 2020Q51NAT2 marksMediumConsider the following language. $L = \{x \in \{a, b\}^*| \text{ number of } a\text{'s in } x \text{ is divisible by 2 but not divisible by 3}\}$ The minimum number of states in a DFA that accepts $L$ is _______.
GATE CSE 2018Q6MCQ1 markEasyLet $N$ be an NFA with $n$ states. Let $k$ be the number of states of a minimal DFA which is equivalent to $N$ . Which one of the following is necessarily true?
GATE CSE 2017 Set 1Q22NAT1 markEasyConsider the language $L$ given by the regular expression $(a+b)^*b(a+b)$ over the alphabet $\{a,b\}$ . The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is _________.
GATE CSE 2017 Set 2Q25NAT1 markMediumThe minimum possible number of states of a deterministic finite automaton that accepts the regular language $L = \{w_1 a w_2 \mid w_1, w_2 \in \{a, b\}^*, |w_1| = 2, |w_2| \ge 3\}$ is ________.
GATE CSE 2017 Set 2Q39MCQ2 marksMediumDiagramLet $\delta$ denote the transition function and $\hat{\delta}$ denote the extended transition function of the $\epsilon$ -NFA whose transition table is given below: Then $\hat{\delta}(q_2, aba)$ is
GATE CSE 2016 Set 1Q18MCQ1 markEasyWhich one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
GATE CSE 2016 Set 2Q16NAT1 markEasyThe number of states in the minimum sized DFA that accepts the language defined by the regular expression $(0+1)^*(0+1)(0+1)^*$ is ___________ .
GATE CSE 2016 Set 2Q42MCQ2 marksMediumConsider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma^*$ . II. There exists a regular language $A$ such that for all languages $B$ , $A \cap B$ is regular. Which one of the following is CORRECT?
GATE CSE 2015 Set 1Q52NAT2 marksMediumDiagramConsider the DFAs M and N given above. The number of states in a minimal DFA that accepts the language $L(M) \cap L(N)$ is ____________
GATE CSE 2015 Set 3Q18MCQ1 markMediumLet L be the language represented by the regular expression $\Sigma^* 0011\Sigma^*$ where $\Sigma = \{0, 1\}$ . What is the minimum number of states in a DFA that recognizes $\overline{\text{L}}$ (complement of L)?
GATE CSE 2014 Set 1Q15MCQ1 markEasyWhich one of the following is TRUE?
GATE CSE 2014 Set 1Q16MCQ1 markEasyDiagramConsider the finite automaton in the following figure. What is the set of reachable states for the input string 0011?
GATE CSE 2014 Set 1Q36MCQ2 marksMediumDiagramWhich of the regular expressions given below represent the following DFA? I) $0^*1(1+00^*1)^*$ II) $0^*1^*1+11^*0^*1$ III) $(0+1)^*1$
GATE CSE 2014 Set 2Q15MCQ1 markEasyIf $L_1 = \{a^n \mid n \ge 0\}$ and $L_2 = \{b^n \mid n \ge 0\}$ , consider (I) $L_1 \cdot L_2$ is a regular language (II) $L_1 \cdot L_2 = \{a^n b^n \mid n \ge 0\}$ Which one of the following is CORRECT?
GATE CSE 2014 Set 2Q36MCQ2 marksHardLet $L_1 = \{w \in \{0,1\}^* \mid w\text{ has at least as many occurrences of } (110)\text{'s as } (011)\text{'s}\}$ . Let $L_2 = \{w \in \{0,1\}^* \mid w\text{ has at least as many occurrences of } (000)\text{'s as } (111)\text{'s}\}$ . Which one of the following is TRUE?
GATE CSE 2014 Set 3Q15NAT1 markMediumThe length of the shortest string NOT in the language (over $\Sigma = \{a, b\}$ ) of the following regular expression is _______. $a^*b^*(ba)^*a^*$
GATE CSE 2013Q8MCQ1 markEasyConsider the languages $L_1 = \Phi$ and $L_2 = \{a\}$ . Which one of the following represents $L_1 L_2^* \cup L_1^*$ ?
GATE CSE 2013Q33MCQ2 marksMediumDiagramConsider the DFA A given below. Which of the following are FALSE? 1. Complement of $L(A)$ is context-free. 2. $L(A) = L((11^*0+0)(0 + 1)^*0^*1^*)$ 3. For the language accepted by $A$ , $A$ is the minimal DFA. 4. $A$ accepts all strings over $\{0, 1\}$ of length at least 2.
GATE CSE 2012Q12MCQ1 markMediumDiagramWhat is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\varepsilon$ is the empty string.
GATE CSE 2012Q25MCQ1 markMediumGiven the language $L = \{ab, aa, baa\}$ , which of the following strings are in $L^*$ ? 1) $abaabaabaa$ 2) $aaaabaaa$ 3) $baaaaabaaab$ 4) $baaaabaa$
GATE CSE 2012Q46MCQ2 marksMediumDiagramConsider the set of strings on $\{0,1\}$ in which, *every substring of 3 symbols* has at most *two* zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The…
GATE CSE 2011Q42MCQ2 marksMediumDefinition of a language $L$ with alphabet $\{a\}$ is given as following. $L = \{a^{nk} \mid k > 0, \text{ and } n \text{ is a positive integer constant}\}$ What is the minimum number of states needed in a DFA to recognize $L$ ?
GATE CSE 2011Q45MCQ2 marksMediumDiagramA deterministic finite automaton (DFA) $D$ with alphabet $\Sigma = \{a, b\}$ is given below. Which of the following finite state machines is a valid minimal DFA which accepts the same language as $D$ ?

Topic guide

What does GATE test in Regular Expressions and Finite Automata?

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
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.
Language Regularity and Language Operations (Complementation / Intersection)
occasional · MCQ · 2 marks · 2026, 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
common · NAT · 2 marks · 2024
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.