GATE CS

Regular expressions and finite automata

Regular languages are exactly the languages that DFAs, NFAs, epsilon-NFAs and regular expressions describe. These notes cover designing and minimising DFAs, the subset construction and its state bound, removing epsilon-moves, regular-expression identities and Arden's rule, the conversions between the forms with their costs, and Moore and Mealy machines.

18 previous-year questions · 17 solved · 5 practice questions

Strings, languages and DFAs

Conventions. $Σ$ is the input alphabet (a finite, non-empty set of symbols), $ε$ is the empty string, $∣ w ∣$ is the length of $w$ , and $Σ^{*}$ is the set of all strings over $Σ$ . A language is any subset of $Σ^{*}$ . $L^{c} = Σ^{*} ∖ L$ is the complement of $L$ with respect to $Σ^{*}$ . Concatenation of languages is $L_{1} L_{2} = {x y ∣ x \in L_{1}, y \in L_{2}}$ and $L^{*} = ⋃_{i \geq 0} L^{i}$ with $L^{0} = {ε}$ .

DFA. A deterministic finite automaton is a 5-tuple $(Q, Σ, δ, q_{0}, F)$ : a finite set of states $Q$ , the alphabet $Σ$ , a transition function $δ : Q \times Σ \to Q$ , a start state $q_{0}$ and accepting states $F \subseteq Q$ . In these notes a DFA is complete: $δ$ is total, so a non-accepting dead (trap) state is counted whenever it is needed. State counts below are for complete DFAs unless said otherwise. In transition tables, → marks the start state and * marks accepting states.

EXTENDED TRANSITION FUNCTION AND LANGUAGE

\hat{δ} (q, ε) = q, \hat{δ} (q, w a) = δ (\hat{δ} (q, w), a), L (M) = {w \in Σ^{*} ∣ \hat{δ} (q_{0}, w) \in F}

A string is accepted if the unique path it traces from $q_{0}$ ends in an accepting state; $ε$ is accepted exactly when $q_{0} \in F$ .

COMPLEMENT OF A DFA LANGUAGE

L (M^{'}) = L (M)^{c} where M^{'} = (Q, Σ, δ, q_{0}, Q ∖ F)

Valid only for a complete DFA. Swapping the accepting states of an NFA does not in general complement its language.

PRODUCT CONSTRUCTION (UNION, INTERSECTION, DIFFERENCE)

∣ Q ∣ \leq m \cdot n states for L (M_{1}) \cap L (M_{2}), L (M_{1}) \cup L (M_{2}), L (M_{1}) ∖ L (M_{2})

Run complete DFAs with $m$ and $n$ states together; states are pairs. Accept when both components accept (intersection), at least one accepts (union), the first accepts and the second does not (difference), or exactly one accepts (symmetric difference).

Minimal complete DFA sizes for common languages (alphabet with at least two symbols)

Language over {a,b} (or {0,1})	States in the minimal complete DFA
$∣ w ∣ \equiv r (mod k)$	$k$
$∣ w ∣ \geq n$	$n + 1$
$∣ w ∣ = n$ exactly	$n + 2$ (one is the dead state)
$w$ ends with a fixed string of length $m$	$m + 1$
$w$ contains a fixed substring of length $m$	$m + 1$
$w$ starts with a fixed string of length $m$	$m + 2$ (one is the dead state)
number of $a$ 's $\equiv r (mod k)$	$k$
number of $a$ 's mod $k$ and number of $b$ 's mod $m$ both fixed	$k m$
binary value of $w$ (most significant bit first, $ε$ has value 0 and is accepted) divisible by odd $k$	$k$ (state = remainder). For even $k$ it can be fewer: $k = 4$ needs 3 (the language is 'ends in 00' or $ε$ or $0$ ...); $k = 2$ needs 2
the $k$ -th symbol from the right is a fixed symbol	$2^{k}$

NUMBER OF DFAS ON N STATES

# DFAs = n^{nk} \cdot 2^{n}

For a fixed set of $n$ labelled states, a fixed start state and an alphabet of $k$ symbols: each of the $nk$ transitions has $n$ choices, and $F$ is any of the $2^{n}$ subsets of $Q$ . This counts machines, not languages; many machines accept the same language. Example: $n = 2$ , $k = 2$ gives $2^{4} \cdot 2^{2} = 64$ .

Designing a DFA for a property

Decide what the machine must remember about the prefix read so far (a remainder, a count capped at a limit, the longest useful suffix, a flag).
Make each distinct piece of memory one state; the start state stands for the empty prefix.
Write $δ$ for every state and every symbol, sending impossible continuations to a dead state.
Mark as accepting every state whose memory satisfies the property.
Test on $ε$ , on a one-symbol string and on a string that nearly satisfies the property.

WORKED EXAMPLE

Design a DFA over ${0, 1}$ accepting the binary strings (most significant bit first) whose value is divisible by 3 (the empty string has value 0 and is accepted). Give its transition table.

Solution

Remember the value of the prefix modulo 3, so the states are $r_{0}, r_{1}, r_{2}$ .
Reading bit $b$ turns value $v$ into $2 v + b$ , so $δ (r_{i}, b) = r_{(2 i + b) mod 3}$ .
From $r_{0}$ : bit 0 gives $0$ , bit 1 gives $1$ . From $r_{1}$ : bit 0 gives $2$ , bit 1 gives $3 mod 3 = 0$ . From $r_{2}$ : bit 0 gives $4 mod 3 = 1$ , bit 1 gives $5 mod 3 = 2$ .
Start and accepting state: $r_{0}$ . Check: $110$ (value 6) goes $r_{0} \to r_{1} \to r_{0} \to r_{0}$ , accepted.

Answer: The transition table is below. Start and accepting state $r_{0}$ . Three states are needed: the three remainders are pairwise distinguishable, so 3 is minimal.

DFA for binary values divisible by 3

State	0	1
→* $r_{0}$	$r_{0}$	$r_{1}$
$r_{1}$	$r_{2}$	$r_{0}$
$r_{2}$	$r_{1}$	$r_{2}$

NFA, epsilon-NFA and the subset construction

NFA. A nondeterministic finite automaton has $δ : Q \times Σ \to 2^{Q}$ : from a state on a symbol it may go to zero, one or several states. A string is accepted if some path ends in an accepting state. A missing transition means the path dies. An $ε$ -NFA also allows moves $δ (q, ε)$ that consume no input.

The $ε$ -closure $ECLOSE (q)$ of a state $q$ is the set of states reachable from $q$ using $ε$ -moves only (including $q$ itself). For a set of states it is the union of the closures of its members.

REMOVING EPSILON-MOVES (EPSILON-NFA TO NFA)

δ^{'} (q, a) = ECLOSE (p \in ECLOSE (q) ⋃ δ (p, a)), q \in F^{'} ⟺ ECLOSE (q) \cap F \neq = \emptyset

Same states and start state. Each new edge stands for ' $ε$ -moves, then $a$ , then $ε$ -moves'; a state becomes accepting if an accepting state can be reached from it by $ε$ -moves alone.

Subset construction (NFA or $\varepsilon$-NFA to DFA)

Start state of the DFA: the $ε$ -closure of ${q_{0}}$ (just ${q_{0}}$ if there are no $ε$ -moves).
For a DFA state $S$ and symbol $a$ : take all NFA states reachable from members of $S$ on $a$ , then take the $ε$ -closure of that set. This is $δ_{D} (S, a)$ .
Build only the subsets reachable from the start; stop when no new subset appears.
A DFA state is accepting if it contains at least one NFA accepting state.
If $\emptyset$ is reached it is the dead state of the DFA.

SIZE BOUND OF THE SUBSET CONSTRUCTION

DFA states \leq 2^{n} for an NFA with n states

The bound is tight: the language 'the $n$ -th symbol from the right is 1' has an $(n + 1)$ -state NFA whose minimal DFA has $2^{n}$ states. Often far fewer subsets are reachable.

DFAs, NFAs and $ε$ -NFAs accept exactly the same class of languages (the regular languages). Nondeterminism changes the number of states needed, not the power.

NFA for the example below (∅ = no move)

State	a	b
→ $p$	${p, q}$	${p}$
$q$	$\emptyset$	${r}$
$r$	$\emptyset$	$\emptyset$

WORKED EXAMPLE

For the NFA over ${a, b}$ in the table above (start $p$ , accepting ${r}$ ), build the reachable part of the equivalent DFA.

Solution

Start: ${p}$ .
${p}$ : on $a$ go to ${p, q}$ ; on $b$ go to ${p}$ .
${p, q}$ : on $a$ go to $δ (p, a) \cup δ (q, a) = {p, q} \cup \emptyset = {p, q}$ ; on $b$ go to ${p} \cup {r} = {p, r}$ .
${p, r}$ : on $a$ go to ${p, q}$ ( $r$ has no move); on $b$ go to ${p}$ .
Only ${p, r}$ contains $r$ , so it is the only accepting state. $\emptyset$ is never reached.

Answer: Three reachable DFA states: {p}, {p,q}, {p,r}, with {p,r} accepting. The language is the set of strings ending in ab.

EXAM TIP

Before building any subset, write the transition table of the NFA once. Do the subset construction row by row from that table, and list only subsets that actually get reached; this saves time and avoids counting unreachable subsets as states.

DFA minimisation

Two states $p, q$ are equivalent if for every string $w$ , $\hat{δ} (p, w)$ is accepting exactly when $\hat{δ} (q, w)$ is accepting. Equivalent states can be merged. For a regular language the minimal complete DFA is unique up to renaming of states.

MINIMAL DFA SIZE (MYHILL–NERODE)

# states of the minimal complete DFA = # equivalence classes of x \sim_{L} y ⟺ \forall z : (x z \in L \Leftrightarrow y z \in L)

Each class of prefixes is one state. $L$ is regular exactly when there are finitely many classes.

Partition-refinement method

Delete every state that is unreachable from the start state.
Make the DFA complete (add a dead state if needed and count it).
Start with two groups: accepting states $F$ and non-accepting states $Q ∖ F$ .
Split a group whenever two of its states, on some symbol, go to different groups.
Repeat until no group splits. Each final group is one state of the minimal DFA.
The new start state is the group of $q_{0}$ ; a group is accepting if its members are accepting.

Table-filling method. Mark every pair ${p, q}$ with exactly one accepting member as distinguishable. Then repeatedly mark ${p, q}$ if for some symbol $a$ the pair ${δ (p, a), δ (q, a)}$ is already marked. Unmarked pairs at the end are equivalent. Both methods give the same answer.

Equivalence of two DFAs. Two DFAs accept the same language exactly when their minimal DFAs are identical up to renaming of states. Equivalently, the product DFA for the symmetric difference reaches no accepting state from its start.

DFA for the example below

State	0	1
→ $A$	$B$	$C$
$B$	$D$	$E$
$C$	$E$	$D$
$D$	$D$	$E$
$E$	$D$	$E$

WORKED EXAMPLE

Find the number of states of the minimal DFA equivalent to the complete DFA over ${0, 1}$ in the table above (start $A$ , accepting ${D, E}$ ).

Solution

All five states are reachable. Initial partition: ${A, B, C}$ and ${D, E}$ .
Refine ${A, B, C}$ : $A$ goes to $B, C$ (both in the first group) on 0 and 1, while $B$ and $C$ go into ${D, E}$ . So $A$ splits off: ${A}, {B, C}, {D, E}$ .
Check ${B, C}$ : both go to ${D, E}$ on 0 and on 1, so they stay together. Check ${D, E}$ : both go to ${D, E}$ on both symbols, so they stay together.
No group splits further.

Answer: 3 states: {A}, {B,C}, {D,E}. The language is the strings of length at least 2.

EXAM TIP

Do not count the dead state twice, and do not forget it: if the question says 'minimal DFA' without qualification, the complete DFA (with a dead state) is meant by convention here. A question that allows missing transitions will say so; then the dead state is dropped and the count is one smaller whenever a dead state was needed.

Regular expressions and their identities

Definition. Regular expressions over $Σ$ are built from $\emptyset$ (language $\emptyset$ ), $ε$ (language ${ε}$ ), each symbol $a \in Σ$ (language ${a}$ ), and, for expressions $r, s$ : union $r + s$ (language $L (r) \cup L (s)$ ), concatenation $r s$ and star $r^{*}$ . Precedence from highest to lowest: star, concatenation, union. So $a b^{*} + c$ means $(a (b^{*})) + c$ . A language is regular exactly when some regular expression denotes it.

Reading a regular expression (over {a,b})

Expression	Language in words
$(a + b)^{*} abb$	strings ending in $abb$
$(a + b)^{} a (a + b)^{}$	strings with at least one $a$
$b^{} (a b^{})^{*}$	all strings, $(a + b)^{*}$
$(b + a b^{} a)^{}$	strings with an even number of $a$ 's
$(aa)^{} + a (aa)^{}$	$a^{*}$

IDENTITIES FOR $\EMPTYSET$ AND $\VAREPSILON$

r + \emptyset = r, r ε = ε r = r, r \emptyset = \emptyset r = \emptyset, \emptyset^{*} = ε^{*} = ε, r + r = r

Union is commutative and associative; concatenation is associative but not commutative.

IDENTITIES FOR STAR

(r^{*})^{*} = r^{*}, r r^{*} = r^{*} r = r^{+}, ε + r r^{*} = r^{*}, (r + ε)^{*} = r^{*}

$r^{+}$ means one or more repetitions.

STAR OF A UNION

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

All five denote the strings formed by any mixture of $r$ -strings and $s$ -strings. $(r + s)^{*}$ is NOT equal to $r^{*} + s^{*}$ .

SHIFTING IDENTITY

r (sr)^{*} = (r s)^{*} r

Both sides are $r$ followed by alternating $s$ , $r$ blocks. $(r s)^{*} \neq = (sr)^{*}$ in general.

DISTRIBUTIVITY

r (s + t) = r s + r t, (s + t) r = sr + t r

Concatenation distributes over union on both sides; union does not distribute over concatenation ( $r + s t \neq = (r + s) (r + t)$ in general).

ARDEN'S RULE

R = Q + R P \Rightarrow R = Q P^{*}, R = Q + P R \Rightarrow R = P^{*} Q

When $ε \in / L (P)$ the stated solution is the unique one. When $ε \in L (P)$ it is still a solution (the smallest) but not the only one. The first form fits Arden's method below, where each equation lists the strings that reach a state.

EXAM TIP

To test an identity, try the shortest strings. $(a + b)^{*} \neq = a^{*} + b^{*}$ because $ab$ is on the left only. $(ab)^{*} \neq = a^{*} b^{*}$ because $abab$ is on the left only. A single counterexample string settles a false identity; a true one needs an argument.

Converting between regular expressions and automata

Regular expression to $\varepsilon$-NFA (Thompson's construction)

Symbol $a$ : two states, start $s$ and accept $f$ , with one edge $s \to f$ labelled $a$ . $ε$ : the same with label $ε$ . $\emptyset$ : two states and no edge.
Union $r + s$ : a new start with $ε$ -edges to the starts of both machines, and $ε$ -edges from both accept states to a new accept state.
Concatenation $r s$ : an $ε$ -edge from the accept state of $r$ to the start of $s$ .
Star $r^{*}$ : a new start and accept state; $ε$ -edges new start to old start, old accept to new accept, new start to new accept, and old accept back to old start.
Every machine built has exactly one start and one accept state; the start state has no incoming edge and the accept state has no outgoing edge.

SIZE OF THOMPSON'S MACHINE

# states \leq 2 m for a regular expression with m symbols and operators

Linear in the length of the expression. Each symbol ( $a$ , $ε$ or $\emptyset$ ) and each union or star adds two states; concatenation adds none.

Automaton to regular expression (state elimination)

Add a new start state with an $ε$ -edge to the old start, and a new accept state with $ε$ -edges from every old accepting state.
Label edges with regular expressions (merge parallel edges by $+$ ).
Eliminate each other state $q$ in turn: for every pair of edges $p x q$ and $q y r$ , add an edge $p \to r$ labelled $x z^{*} y$ , where $z$ is the label of the loop on $q$ (omit $z^{*}$ if there is no loop); merge with any existing $p \to r$ edge using $+$ .
When only the new start and accept state remain, the label on the edge between them is the answer.

Arden's method. Write one equation per state, $q_{i} = \sum_{j} q_{j} a_{j i}$ (plus $ε$ for the start state), where $q_{j} a_{j i}$ means 'reach $q_{j}$ , then read the symbol on the edge $q_{j} \to q_{i}$ '. Solve by substitution using the form $R = Q + R P \Rightarrow R = Q P^{*}$ . The regular expression is the sum of the solved variables of the accepting states.

DFA for the example below

State	0	1
→* $q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	$q_{1}$	$q_{0}$

WORKED EXAMPLE

Find a regular expression for the language of the DFA over ${0, 1}$ in the table above (start and accepting state $q_{0}$ ).

Solution

Write the equations for the strings that reach each state: $q_{0} = ε + q_{0} 0 + q_{1} 1$ and $q_{1} = q_{0} 1 + q_{1} 0$ .
Apply Arden to $q_{1} = q_{0} 1 + q_{1} 0$ (here $Q = q_{0} 1$ , $P = 0$ ): $q_{1} = q_{0} 1 0^{*}$ .
Substitute into $q_{0}$ : $q_{0} = ε + q_{0} 0 + q_{0} 1 0^{*} 1 = ε + q_{0} (0 + 1 0^{*} 1)$ .
Apply Arden again ( $Q = ε$ , $P = 0 + 1 0^{*} 1$ , and $ε \in / L (P)$ ): $q_{0} = (0 + 1 0^{*} 1)^{*}$ . Only $q_{0}$ accepts.

Answer: $(0 + 1 0^{*} 1)^{*}$ , the strings with an even number of 1's.

Costs of conversions (worst case)

Conversion	Size of the result
regular expression to $ε$ -NFA	linear: at most $2 m$ states
$ε$ -NFA to NFA (remove $ε$ -moves)	same number of states, possibly more edges
NFA with $n$ states to DFA	up to $2^{n}$ states (tight)
DFA to regular expression	can be exponentially larger in the worst case
complete DFA to the DFA of its complement	same number of states

Moore and Mealy machines

These are finite automata with output instead of accept/reject. Both have a finite input alphabet $Σ$ , an output alphabet $Δ$ , a transition function $δ : Q \times Σ \to Q$ and a start state; the output function differs.

Moore versus Mealy

Feature	Moore machine	Mealy machine
Output function	$λ : Q \to Δ$ (output attached to the state)	$λ : Q \times Σ \to Δ$ (output attached to the transition)
Output on input of length $n$	$n + 1$ symbols (the start state's output comes first)	$n$ symbols
Output on $ε$	the start state's output	empty string
Reacts to a new input symbol	after the move, in the next state	immediately, on the same transition

OUTPUT LENGTH

∣ out_{Moore} (w) ∣ = ∣ w ∣ + 1, ∣ out_{Mealy} (w) ∣ = ∣ w ∣

Holds for every input $w$ because both machines are deterministic and complete.

Equivalence. A Mealy machine and a Moore machine are equivalent when the Moore output, ignoring its first symbol, equals the Mealy output on every input. Every Moore machine converts to a Mealy machine with the same states (give each transition the output of its target state). Every Mealy machine converts to a Moore machine, but the number of states may grow, to at most (number of states) $\times$ (number of distinct outputs).

Mealy machine for the example below (next state/output)

State	0	1
→ $A$	$B /0$	$A /0$
$B$	$B /0$	$A /1$

WORKED EXAMPLE

For the Mealy machine over ${0, 1}$ in the table above (start $A$ ), give its output on input $1001101$ .

Solution

Start in $A$ . Read 1: go to $A$ , output 0.
Read 0: go to $B$ , output 0. Read 0: stay in $B$ , output 0.
Read 1: go to $A$ , output 1. Read 1: stay in $A$ , output 0.
Read 0: go to $B$ , output 0. Read 1: go to $A$ , output 1.

Answer: 0001001 (seven symbols; the machine outputs 1 exactly when a 1 follows a 0).

EXAM TIP

A Moore machine's output string is one symbol longer than the input. When a question gives the output of a Moore machine, count the extra first symbol before comparing lengths.

PREVIOUS-YEAR QUESTIONS

18 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS1 Q.26

GATE 2026 · CS1Q.26 · 1 mark · MSQ

Let $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$ ?

(A)
32
(B)
65
(C)
1
(D)
128

Answer and solution

GATE 2026 CS1 Q.26: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.26: answer and solution

GATE 2026 CS2 Q.47

GATE 2026 · CS2Q.47 · 2 marks · MSQ

Consider the following two finite automata $D_{1}$ and $D_{2}$ .

Which of the following statements is/are true?

GATE 2026 CS2 question 47: Two state diagrams over 0,1. — Figure from the GATE 2026 CS2 paper. It is part of the question.

(A)
$L (D_{1}) = L (D_{2})$
(B)
$L (D_{1})$ is a proper subset of $L (D_{2})$
(C)
$L (D_{1}) \cap L (D_{2}) = {ϵ}$
(D)
$(L (D_{1}) \cup L (D_{2}))^{*}$ consists of all strings in ${0, 1}^{*}$ whose length is divisible by 3

Answer and solution

GATE 2026 CS2 Q.47: answer and solution

GATE 2025 CS1 Q.28

GATE 2025 · CS1Q.28 · 1 mark · MSQ

A regular language $L$ is accepted by a non-deterministic finite automaton (NFA) with $n$ states. Which of the following statement(s) is/are FALSE?

(A)
$L$ may have an accepting NFA with $< n$ states.
(B)
$L$ may have an accepting DFA with $< n$ states.
(C)
There exists a DFA with $\leq 2^{n}$ states that accepts $L$ .
(D)
Every DFA that accepts $L$ has $> 2^{n}$ states.

Answer and solution

GATE 2025 CS1 Q.28: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.28: answer and solution

GATE 2025 CS1 Q.50

GATE 2025 · CS1Q.50 · 2 marks · MSQ

Consider the following deterministic finite automaton (DFA) defined over the alphabet, $Σ = {a, b}$ . Identify which of the following language(s) is/are accepted by the given DFA.

GATE 2025 CS1 question 50: A DFA with four states in a row, left to right: q_0 (start, arrow entering from the left), q_1, q_2, q_3 (q_3 is… — Figure from the GATE 2025 CS1 paper. It is part of the question.

(A)
The set of all strings containing an even number of $b$ 's.
(B)
The set of all strings containing the pattern $bab$ .
(C)
The set of all strings ending with the pattern $bab$ .
(D)
The set of all strings not containing the pattern $aba$ .

Answer and solution

GATE 2025 CS1 Q.50: answer and solution

GATE 2025 CS2 Q.60

GATE 2025 · CS2Q.60 · 2 marks · NAT

Let $Σ = {1, 2, 3, 4}$ . For $x \in Σ^{*}$ , let $p r o d (x)$ be the product of symbols in $x$ modulo 7. We take $p r o d (ϵ) = 1$ , where $ϵ$ is the null string.

For example, $p r o d (124) = (1 \times 2 \times 4) mod 7 = 1$ .

Define $L = {x \in Σ^{*} ∣ p r o d (x) = 2}$ .

The number of states in a minimum state DFA for $L$ is ___________. (Answer in integer)

Answer and solution

GATE 2025 CS2 Q.60: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.60: answer and solution

GATE 2024 CS1 Q.50

GATE 2024 · CS1Q.50 · 2 marks · MSQ

Consider 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 2024 CS1 question 50: DFA with states 1, 2, 3, 4, 5. — Figure from the GATE 2024 CS1 paper. It is part of the question.

(A)
States 2 and 4 are distinguishable in M
(B)
States 3 and 4 are distinguishable in M
(C)
States 2 and 5 are distinguishable in M
(D)
Any string w with n_0(w) = n_1(w) is in L(M)

Answer and solution

GATE 2024 CS1 Q.50: answer and solution

GATE 2024 CS1 Q.61

GATE 2024 · CS1Q.61 · 2 marks · NAT

Consider the following two regular expressions over the alphabet ${0, 1}$ :

$r = 0^{*} + 1^{*}$

$s = 0 1^{*} + 1 0^{*}$

The total number of strings of length less than or equal to 5, which are neither in $r$ nor in $s$ , is ______.

Answer and solution

GATE 2024 CS1 Q.61: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.61: answer and solution

GATE 2024 CS2 Q.22

GATE 2024 · CS2Q.22 · 1 mark · MCQ

Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?

GATE 2024 CS2 question 22: A DFA with two states. — Figure from the GATE 2024 CS2 paper. It is part of the question.

(A)
$0^{*} 1 (0 + 1 0^{*} 1)^{*}$
(B)
$0^{*} (1 0^{*} 11)^{*} 0^{*}$
(C)
$0^{*} 1 (01 0^{*} 1)^{*} 0^{*}$
(D)
$0 (1 + 0^{*} 1 0^{*} 1)^{*} 0^{*}$

Answer and solution

GATE 2024 CS2 Q.22: answer and solution

GATE 2024 CS2 Q.41

GATE 2024 · CS2Q.41 · 2 marks · MCQ

Let $M$ be the 5-state NFA with $ε$ -transitions shown in the diagram below. Which one of the following regular expressions represents the language accepted by $M$ ?

GATE 2024 CS2 question 41: States 1 to 5. — Figure from the GATE 2024 CS2 paper. It is part of the question.

(A)
$(00)^{*} + 1 (11)^{*}$
(B)
$0^{*} + (1 + 0 (00)^{*}) (11)^{*}$
(C)
$(00)^{*} + (1 + (00)^{*}) (11)^{*}$
(D)
$0^{+} + 1 (11)^{*} + 0 (11)^{*}$

Answer and solution

GATE 2024 CS2 Q.41: answer and solution

GATE 2024 CS2 Q.62

GATE 2024 · CS2Q.62 · 2 marks · NAT

Let $L_{1}$ be the language represented by the regular expression $b^{*} a b^{*} (a b^{*} a b^{*})^{*}$ and $L_{2} = {w \in (a + b)^{*} ∣ ∣ w ∣ \leq 4}$ , where $∣ w ∣$ denotes the length of string $w$ . The number of strings in $L_{2}$ which are also in $L_{1}$ is ______.

Answer and solution

GATE 2024 CS2 Q.62: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.62: answer and solution

Show the other 8 questions

GATE 2023 CS Q.14

GATE 2023 · CSQ.14 · 1 mark · MCQ

Consider the Deterministic Finite-state Automaton (DFA) $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 language accepted by $A$ ?

GATE 2023 CS question 14: State diagram with states s, p, q, r. — Figure from the GATE 2023 CS paper. It is part of the question.

(A)
$1 (0^{*} 11)^{*}$
(B)
$0 (0 + 1)^{*}$
(C)
$1 (0 + 11)^{*}$
(D)
$1 (11 0^{*})^{*}$

Answer and solution

GATE 2023 CS Q.14: answer and solution

GATE 2023 CS Q.19

GATE 2023 · CSQ.19 · 1 mark · MCQ

Consider the following definition of a lexical token id for an identifier in a programming language, using extended regular expressions:

letter → [A-Za-z]
digit → [0-9]
id → letter (letter | digit)*

Which one of the following Non-deterministic Finite-state Automata with ε-transitions accepts the set of valid identifiers? (A double-circle denotes a final state)

GATE 2023 CS question 19: Four NFAs with ε-transitions, each starting from a start state (arrow in). — Figure from the GATE 2023 CS paper. It is part of the question.

(A)
Figure — NFA (A) as described
(B)
Figure — NFA (B) as described
(C)
Figure — NFA (C) as described
(D)
Figure — NFA (D) as described

Answer and solution

GATE 2023 CS Q.19: answer and solution

GATE 2023 CS Q.63

GATE 2023 · CSQ.63 · 2 marks · NAT

Consider the language $L$ over the alphabet ${0, 1}$ , given below:

L = {w \in {0, 1}^{*} ∣ w does not contain three or more consecutive 1’s} .

The minimum number of states in a Deterministic Finite-State Automaton (DFA) for $L$ is ______.

Answer and solution

GATE 2023 CS Q.63: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.63: answer and solution

GATE 2022 CS Q.12

GATE 2022 · CSQ.12 · 1 mark · MCQ

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

GATE 2022 CS question 12: A DFA with three states. — Figure from the GATE 2022 CS paper. It is part of the question.

(A)
$a b^{*} ba b^{*} + b a^{*} ab a^{*}$
(B)
$(a b^{*} b)^{*} a b^{*} + (b a^{*} a)^{*} b a^{*}$
(C)
$(a b^{*} b + b a^{*} a)^{*} (a^{*} + b^{*})$
(D)
$(b a^{*} a + a b^{*} b)^{*} (a b^{*} + b a^{*})$

Answer and solution

GATE 2022 CS Q.12: answer and solution

GATE 2020 CS Q.7

GATE 2020 · CSQ.7 · 1 mark · MCQ

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?

(A)
((0 + 1)*1(0 + 1)*1)10
(B)
(0*10*10*)*0*1
(C)
10*(0*10*10*)*
(D)
(0*10*10*)10

Official answer

Official answer: marks to all candidatesSource: Official answer key, GATE 2020 CS (IIT Delhi)

See the question in the paper

Tap to open full size

GATE 2020 CS Q.7: official answer

GATE 2020 CS Q.51

GATE 2020 · CSQ.51 · 2 marks · NAT

Consider the following language.

$L = {x \in {a, b}^{*} ∣ number of a ’s in x is divisible by 2 but not divisible by 3}$

The minimum number of states in a DFA that accepts $L$ is ______.

Answer and solution

GATE 2020 CS Q.51: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.51: answer and solution

GATE 2018 CS Q.6

GATE 2018 · CSQ.6 · 1 mark · MCQ

Let $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?

(A)
$k \geq 2^{n}$
(B)
$k \geq n$
(C)
$k \leq n^{2}$
(D)
$k \leq 2^{n}$

Answer and solution

GATE 2018 CS Q.6: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.6: answer and solution

GATE 2018 CS Q.52

GATE 2018 · CSQ.52 · 2 marks · NAT

Given a language $L$ , define $L^{i}$ as follows:
$L^{0} = {ε}$
$L^{i} = L^{i - 1} \cdot L for all i > 0$
The order of a language $L$ is defined as the smallest $k$ such that $L^{k} = L^{k + 1}$ . Consider the language $L_{1}$ (over alphabet 0) accepted by the following automaton. The order of $L_{1}$ is ______.

GATE 2018 CS question 52: State diagram with three states in a row. — Figure from the GATE 2018 CS paper. It is part of the question.

Answer and solution

GATE 2018 CS Q.52: answer and solution

OTHER EXAMS

ISRO: 5 questions

From ISRO's Scientist/Engineer written test: ISRO CS 2025, ISRO CS 2023. They are not counted in the GATE numbers on this page.

ISRO CS 2025 Q.28

ISRO 2025 · CSQ.28 · 1 mark · MCQ

Which of the following hexadecimal constants match the regular expression given? (0x[0-9A-F]+)

(A)
0x4C5
(B)
0x50b
(C)
04A
(D)
0x

Answer and solution

ISRO CS 2025 Q.28: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.28: answer and solution

ISRO CS 2025 Q.78

ISRO 2025 · CSQ.78 · 1 mark · MCQ

78. Consider the regular expression $R$ over the alphabet ${a, b}$ : $(a^{*} b)^{*} + (b^{*} a)^{*}$ . Which of the following regular expressions below describe the same language as $R$ ?

(A)
$(a^{*} b^{*}) + (b^{*} a^{*})$
(B)
$a^{*} + b^{*}$
(C)
$(a + b)^{*}$
(D)
$a^{*} b + b^{*} a$

Answer and solution

ISRO CS 2025 Q.78: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.78: answer and solution

ISRO CS 2025 Q.79

ISRO 2025 · CSQ.79 · 1 mark · MCQ

Consider the deterministic finite-state automaton (DFA) below over the alphabet {a,b}. The state with a small incoming arrow is the initial state, while a double circle state denotes a final state. The number of states in the MINIMAL DFA for the language accepted by this DFA is:

ISRO CS 2025 question 79: A DFA with three states. — Figure from the ISRO CS 2025 paper. It is part of the question.

(A)
1
(B)
2
(C)
3
(D)
4

Answer and solution

ISRO CS 2025 Q.79: answer and solution

ISRO CS 2023 Q.55

ISRO 2023 · CSQ.55 · 1 mark · MCQ

Consider the deterministic finite-state automaton (DFA) below. The alphabet is {a, b}. The state with a small incoming arrow is the initial state, while the double circle state denotes a final state. Which of the following regular expressions defines the language accepted by the DFA?

ISRO CS 2023 question 55: A DFA with three states. — Figure from the ISRO CS 2023 paper. It is part of the question.

(A)
ab*
(B)
a*b*
(C)
(ab)*
(D)
a*b

Answer and solution

ISRO CS 2023 Q.55: answer and solution

ISRO CS 2023 Q.56

ISRO 2023 · CSQ.56 · 1 mark · MCQ

Consider the Nondeterministic Finite-State Automaton (NFA) below. States with a small incoming arrow are initial states, while a double circle state denotes a final state. The number of states in the MINIMAL Deterministic Finite-State Automaton (DFA) for this language is:

ISRO CS 2023 question 56: An NFA with three states in a row, left to right. — Figure from the ISRO CS 2023 paper. It is part of the question.

(A)
2
(B)
4
(C)
6
(D)
8

Answer and solution

ISRO CS 2023 Q.56: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 12 marks · MCQ

Let $L$ be the set of strings over ${0, 1}$ in which the number of 0's is even and the number of 1's is divisible by 3. How many states does the minimal complete DFA for $L$ have?

(A)
5
(B)
6
(C)
8
(D)
9

Answer and solution

Answer: (B)

Track the pair (number of 0's mod 2, number of 1's mod 3). This gives $2 \times 3 = 6$ states, all reachable; the accepting state is $(0, 0)$ .
Take two different pairs $(i, j) \neq = (i^{'}, j^{'})$ . Appending $z = 0^{i} 1^{(3 - j) mod 3}$ takes $(i, j)$ to $(0, 0)$ , which accepts, and takes $(i^{'}, j^{'})$ to $((i^{'} + i) mod 2, (j^{'} - j) mod 3)$ , which is not $(0, 0)$ because $(i^{'}, j^{'}) \neq = (i, j)$ .
So every two states are distinguishable, no two merge, and the minimal DFA has 6 states.

PRACTICE 22 marks · NAT

Let $L$ be the set of strings over ${0, 1}$ whose 4th symbol from the right is 1 (strings shorter than 4 symbols are not in $L$ ). What is the number of states of the minimal complete DFA for $L$ ?

Answer and solution

Answer: $16$

After reading a string the machine must remember its last 4 symbols; strings shorter than 4 behave like strings padded on the left with 0's, since a missing symbol can never be the required 1.
There are $2^{4} = 16$ possible last-four patterns and all are reachable.
Two different patterns differ in some position $i$ from the right ( $1 \leq i \leq 4$ ); appending $4 - i$ symbols shifts that position into the 4th place from the right, so one string is accepted and the other is not.
Hence all 16 states are distinguishable and the minimum is $2^{4} = 16$ .

PRACTICE 31 mark · NAT

A Mealy machine over ${0, 1}$ has states $S$ (start), $P_{0}$ and $P_{1}$ ; the state records the previous input symbol ( $S$ means no symbol read yet). On each input symbol it outputs 1 if the symbol equals the previous input symbol and 0 otherwise (the first symbol always gives output 0). How many 1's are in the output for the input $0110011$ ?

Answer and solution

Answer: $3$

Compare each symbol with the one before it: 0 (first, output 0); 1 vs 0 gives 0; 1 vs 1 gives 1; 0 vs 1 gives 0; 0 vs 0 gives 1; 1 vs 0 gives 0; 1 vs 1 gives 1.
The output is 0010101, which contains three 1's.

PRACTICE 42 marks · MSQ

Over $Σ = {a, b}$ , which of the following equalities between regular expressions hold?

(A)
$(a + b)^{*} = (a^{*} b^{*})^{*}$
(B)
$(ab)^{*} a = a (ba)^{*}$
(C)
$(a + b)^{*} = a^{*} + b^{*}$
(D)
$(a^{*} b)^{*} = ε + (a + b)^{*} b$

Answer and solution

Answer: (A), (B), (D)

A holds: $(r + s)^{*} = (r^{*} s^{*})^{*}$ with $r = a, s = b$ .
B holds: it is the shifting identity $r (sr)^{*} = (r s)^{*} r$ with $r = a, s = b$ .
C fails: $ab$ is in $(a + b)^{*}$ but is neither all $a$ 's nor all $b$ 's.
D holds: $(a^{*} b)^{*}$ is a concatenation of blocks each ending in $b$ , so it is $ε$ or a string ending in $b$ ; conversely every string ending in $b$ splits after each of its $b$ 's into such blocks.

PRACTICE 51 mark · MCQ

An NFA over ${a, b}$ has states $p, q, r$ , start $p$ , accepting ${r}$ , and transitions $δ (p, a) = {p, q}$ , $δ (p, b) = {p}$ , $δ (q, a) = {r}$ , $δ (q, b) = {r}$ ( $r$ has no moves). How many states does the subset-construction DFA have if only subsets reachable from the start are built?

(A)
2
(B)
3
(C)
4
(D)
8

Answer and solution

Answer: (C)

Start ${p}$ : on $a$ it goes to ${p, q}$ , on $b$ back to ${p}$ .
${p, q}$ : on $a$ to ${p, q} \cup {r} = {p, q, r}$ ; on $b$ to ${p} \cup {r} = {p, r}$ .
${p, q, r}$ : on $a$ to ${p, q, r}$ ; on $b$ to ${p, r}$ . ${p, r}$ : on $a$ to ${p, q}$ ; on $b$ to ${p}$ .
No new subset appears and $\emptyset$ is not reached, so the reachable DFA has 4 states. (The language is 'the second symbol from the right is $a$ ', which needs $2^{2} = 4$ states.)

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Regular expressions and finite automata

Preparing in Kolkata? IAE Academy's course for GATE CSE.