Regular Expressions, Finite Automata and Regular Languages: GATE CS previous year questions (Theory of Computation)

GATE CS 2026 Set 1MSQ1 markEasy (estimate)
GATE CS 2026 Set 1, Q.26
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 determini...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2026 Set 2MSQ2 marksMedium (estimate)
GATE CS 2026 Set 2, Q.47
Consider the following two finite automata $D_{1}$ and $D_{2}$ . Two finite automata D1 and D2 over alphabet {0, 1}. D1 accepts strings formed by concatenating {000, 001, 010, 101},...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2025 Set 1MSQ1 markEasy (estimate)
GATE CS 2025 Set 1, Q.28
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?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2025 Set 1MCQ2 marksMedium (estimate)
GATE CS 2025 Set 1, Q.44
Consider the following two languages over the alphabet ${a, b}$ : $L_{1} = {α β α ∣ α \in {a, b}^{+} AND β \in {a, b}^{+}}$ …
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2025 Set 1MSQ2 marksMedium (estimate)
GATE CS 2025 Set 1, Q.50
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 gi...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2025 Set 2MSQ1 markEasy (estimate)
GATE CS 2025 Set 2, Q.30
Consider the two lists List I and List II given below: List I List II (i) Context free languages (a) Closed under union (ii) Recursive languages (b) Not closed under complementa...
Context-Free Grammars, Pushdown Automata and CFLs · Decidability, Reducibility and Undecidability · Regular Expressions, Finite Automata and Regular Languages
GATE CS 2025 Set 2MSQ2 marksEasy (estimate)
GATE CS 2025 Set 2, Q.52
Let $Σ = {a, b, c}$ . For $x \in Σ^{*}$ , and $α \in Σ$ , let $#_{α} (x)$ denote the number of occurrences of $α$ in $x$ . Which one or more of the follo...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2025 Set 2NAT2 marksMedium (estimate)
GATE CS 2025 Set 2, Q.60
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...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2024 Set 1MSQ1 markEasy (estimate)
GATE CS 2024 Set 1, Q.23
Let $L_{1}, L_{2}$ be two regular languages and $L_{3}$ a language which is not regular. Which of the following statements is/are always TRUE?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2024 Set 1MSQ2 marksMedium (estimate)
GATE CS 2024 Set 1, Q.50
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…
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2024 Set 1NAT2 marksMedium (estimate)
GATE CS 2024 Set 1, Q.61
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,...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2024 Set 2MCQ1 markEasy (estimate)
GATE CS 2024 Set 2, Q.22
Which one of the following regular expressions is equivalent to the language accepted by the DFA given below? A 2-state DFA where the left initial state has a self-loop on 0 and...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2024 Set 2MCQ2 marksMedium (estimate)
GATE CS 2024 Set 2, Q.41
Let $M$ be the 5-state NFA with $ϵ$ -transitions shown in the diagram below. A 5-state NFA M with states 1 to 5: state 1 is the start state with epsilon transitions to sta...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2024 Set 2NAT2 marksEasy (estimate)
GATE CS 2024 Set 2, Q.62
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…
Regular Expressions, Finite Automata and Regular Languages · Combinatorics, Counting, Recurrence Relations and Generating Functions
GATE CS 2023MCQ1 markEasy (estimate)
GATE CS 2023, Q.14
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 st...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2023MSQ1 markEasy (estimate)
GATE CS 2023, Q.24
Which of the following statements is/are CORRECT?
Turing Machines and Chomsky Hierarchy · Regular Expressions, Finite Automata and Regular Languages · Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2023NAT2 marksEasy (estimate)
GATE CS 2023, Q.63
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 numb...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2022MCQ1 markMedium (estimate)
GATE CS 2022, Q.12
Which one of the following regular expressions correctly represents the language of the finite automaton given below? Finite automaton with start state q0 and two accepting stat...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2022MSQ2 marksMedium (estimate)
GATE CS 2022, Q.47
Consider the following languages: $L_{1} = {a^{n} w a^{n} ∣ w \in {a, b}^{*}}$ $L_{2} = {w x w^{R} ∣ w, x \in {a, b}^{*}, ∣ w ∣, ∣ x ∣ > 0}$ Note that $w^{R}$ is the reversal of t...
Regular Expressions, Finite Automata and Regular Languages · Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2021 Set 1MCQ2 marksEasy (estimate)
GATE CS 2021 Set 1, Q.48 (CS Q.38)
Consider the following language. $L = {w \in {0, 1}^{*} ∣ w ends with the substring 011}$ Which one of the following deterministic finite automata accepts $L$ ?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2021 Set 2MCQ1 markEasy (estimate)
GATE CS 2021 Set 2, Q.19 (CS Q.9)
Let $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 mi...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2021 Set 2NAT1 markEasy (estimate)
GATE CS 2021 Set 2, Q.27 (CS Q.17)
Consider the following deterministic finite automaton (DFA). A 6-state deterministic finite automaton where start state q0 transitions on 0 to q1 and on 1 to q2; q1 transitions...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2021 Set 2MSQ2 marksMedium (estimate)
GATE CS 2021 Set 2, Q.57 (CS Q.47)
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $ϵ$ is divisible by three.
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2020MCQ1 markMedium (estimate)
GATE CS 2020, Q.17 (CS Q.7)
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2020MCQ1 markEasy (estimate)
GATE CS 2020, Q.18 (CS Q.8)
Consider the following statements. I. If $L_{1} \cup L_{2}$ is regular, then both $L_{1}$ and $L_{2}$ must be regular. II. The class of regular languages is closed under infinite union....
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2020MCQ2 marksHard (estimate)
GATE CS 2020, Q.42 (CS Q.32)
Consider the following languages. $L_{1} L_{2} = {w x y x ∣ w, x, y \in (0 + 1)^{+}} = {x y ∣ x, y \in (a + b)^{*}, ∣ x ∣ = ∣ y ∣, x \neq = y}$ W...
Regular Expressions, Finite Automata and Regular Languages · Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2020NAT2 marksMedium (estimate)
GATE CS 2020, Q.61 (CS Q.51)
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 stat...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2019MCQ1 markEasy (estimate)
GATE CS 2019, Q.17 (CS Q.7)
If $L$ is a regular language over $Σ = {a, b}$ , which one of the following languages is NOT regular?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2019MCQ1 markMedium (estimate)
GATE CS 2019, Q.25 (CS Q.15)
For $Σ = {a, b}$ , let us consider the regular language $L = {x ∣ x = a^{2 + 3 k} or x = b^{10 + 12 k}, k \geq 0}$ . Which one of the following can be a pumping len...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2019NAT2 marksHard (estimate)
GATE CS 2019, Q.58 (CS Q.48)
Let $Σ$ be the set of all bijections from ${1, \dots, 5}$ to ${1, \dots, 5}$ , where $i d$ denotes the identity function, i.e. $i d (j) = j, \forall j$ . Let $\circ$ deno...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2018MCQ1 markEasy (estimate)
GATE CS 2018, Q.16 (CS Q.6)
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?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2018NAT2 marksMedium (estimate)
GATE CS 2018, Q.62 (CS Q.52)
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 lang...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2017 Set 1NAT1 markEasy (estimate)
GATE CS 2017 Set 1, Q.22 (CS Q.22)
Consider 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 au...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2017 Set 1MCQ2 marksEasy (estimate)
GATE CS 2017 Set 1, Q.37 (CS Q.37)
Consider the context-free grammars over the alphabet ${a, b, c}$ given below. $S$ and $T$ are non-terminals. $G_{1} : S \to a S b ∣ T, T \to c T ∣ ϵ$ …
Context-Free Grammars, Pushdown Automata and CFLs · Regular Expressions, Finite Automata and Regular Languages
GATE CS 2017 Set 2NAT1 markMedium (estimate)
GATE CS 2017 Set 2, Q.25 (CS Q.25)
The minimum possible number of states of a deterministic finite automaton that accepts the regular language…
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2017 Set 2MCQ2 marksMedium (estimate)
GATE CS 2017 Set 2, Q.39 (CS Q.39)
Let $δ$ denote the transition function and $δ^$ denote the extended transition function of the $ϵ$ -NFA whose transition table is given below: | $δ$ |...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2016 Set 1MCQ1 markEasy (estimate)
GATE CS 2016 Set 1, Q.28 (CS Q.18)
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2016 Set 2NAT1 markEasy (estimate)
GATE CS 2016 Set 2, Q.26 (CS Q.16)
The number of states in the minimum sized DFA that accepts the language defined by the regular expression $(0 + 1)^{*} (0 + 1) (0 + 1)^{*}$ is ________.
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2016 Set 2MCQ1 markEasy (estimate)
GATE CS 2016 Set 2, Q.27 (CS Q.17)
Language $L_{1}$ is defined by the grammar: $S_{1} \to a S_{1} b ∣ ε$ Language $L_{2}$ is defined by the grammar: $S_{2} \to ab S_{2} ∣ ε$ Consider the following...
Regular Expressions, Finite Automata and Regular Languages · Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2016 Set 2MCQ1 markMedium (estimate)
GATE CS 2016 Set 2, Q.28 (CS Q.18)
Consider the following types of languages: $L_{1}$ : Regular, $L_{2}$ : Context-free, $L_{3}$ : Recursive, $L_{4}$ : Recursively enumerable. Which of the following is/are TRUE? I.…
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2016 Set 2MCQ2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.52 (CS Q.42)
Consider the following two statements: I. If all states of an NFA are accepting states then the language accepted by the NFA is $Σ^{*}$ . II. There exists a regular language…
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2015 Set 1NAT2 marksEasy (estimate)
GATE CS 2015 Set 1, Q.62 (CS Q.52)
Consider the DFAs $M$ and $N$ given below. State transition diagrams for DFAs M and N, accepting strings ending in a and b respectively State transition diagrams of DFAs M and N...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2015 Set 2MCQ2 marksEasy (estimate)
GATE CS 2015 Set 2, Q.45 (CS Q.35)
Consider the alphabet $Σ = {0, 1}$ , the null/empty string $λ$ and the sets of strings $X_{0}, X_{1}$ , and $X_{2}$ generated by the corresponding non-terminals of a regula...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2015 Set 2MCQ2 marksMedium (estimate)
GATE CS 2015 Set 2, Q.61 (CS Q.51)
Which of the following languages is/are regular? $L_{1} = {w x w^{R} ∣ w, x \in {a, b}^{+} and ∣ w ∣, ∣ x ∣ > 0}$ , $w^{R}$ is the reverse of string $w$ …
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2015 Set 2NAT2 marksEasy (estimate)
GATE CS 2015 Set 2, Q.63 (CS Q.53)
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0 + 1)^{*} (10)$ is _____.
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2015 Set 3MCQ1 markMedium (estimate)
GATE CS 2015 Set 3, Q.28 (CS Q.18)
Let $L$ be the language represented by the regular expression $Σ^{*} 0011 Σ^{*}$ where $Σ = {0, 1}$ . What is the minimum number of states in a DFA that recognizes…
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2014 Set 1MCQ1 markEasy (estimate)
GATE CS 2014 Set 1, Q.25 (CS Q.15)
Which one of the following is TRUE?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2014 Set 1MCQ1 markEasy (estimate)
GATE CS 2014 Set 1, Q.26 (CS Q.16)
Consider the finite automaton in the following figure. Non-deterministic finite automaton with four states q0, q1, q2, and q3 What is the set of reachable states for the input s...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2014 Set 1MCQ2 marksMedium (estimate)
GATE CS 2014 Set 1, Q.46 (CS Q.36)
Which of the regular expressions given below represent the following DFA? Deterministic finite automaton with two states accepting binary strings I) $0^{*} 1 (1 + 0 0^{*} 1)^{*}$ II)…
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2014 Set 2MCQ1 markEasy (estimate)
GATE CS 2014 Set 2, Q.25 (CS Q.15)
If $L_{1} = {a^{n} ∣ n \geq 0}$ and $L_{2} = {b^{n} ∣ n \geq 0}$ , consider (I) $L_{1} \cdot L_{2}$ is a regular language (II) $L_{1} \cdot L_{2} = {a^{n} b^{n} ∣ n \geq 0}$ Which one of...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2014 Set 2MCQ2 marksHard (estimate)
GATE CS 2014 Set 2, Q.46 (CS Q.36)
Let $L_{1} = {w \in {0, 1}^{*} ∣ w has at least as many occurrences of (110) ’s as (011) ’s}$ . Let…
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2014 Set 3NAT1 markMedium (estimate)
GATE CS 2014 Set 3, Q.25 (CS Q.15)
The length of the shortest string NOT in the language (over $Σ = {a, b}$ ) of the following regular expression is _____. $a^{*} b^{*} (ba)^{*} a^{*}$
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2013MCQ1 markEasy (estimate)
GATE CS 2013, Q.8 (CS Q.8)
Consider the languages $L_{1} = Φ$ and $L_{2} = {a}$ . Which one of the following represents $L_{1} L_{2}^{*} \cup L_{1}^{*}$ ?
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2013MCQ2 marksMedium (estimate)
GATE CS 2013, Q.33 (CS Q.33)
Consider the DFA A given below. Deterministic finite automaton with three states and transitions on symbols 0 and 1 Which of the following are FALSE? 1. Complement of $L (A)$ is...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2012MCQ1 markEasy (estimate)
GATE CS 2012, Q.12 (CS Q.12)
What is the complement of the language accepted by the NFA shown below? Assume $Σ = {a}$ and $ε$ is the empty string. Non-deterministic finite automaton with th...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2012MCQ1 markMedium (estimate)
GATE CS 2012, Q.24 (CS Q.24)
Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If $L$ is a context-free language, then, is $L$ also context-free? 3...
Decidability, Reducibility and Undecidability · Regular Expressions, Finite Automata and Regular Languages
GATE CS 2012MCQ1 markEasy (estimate)
GATE CS 2012, Q.25 (CS Q.25)
Given the language $L = {ab, aa, baa}$ , which of the following strings are in $L^{*}$ ? 1) abaabaaabaa 2) aaaabaaaa 3) baaaaabaaaab 4) baaaaabaa
Regular Expressions, Finite Automata and Regular Languages · Regular Expressions, Finite Automata and Regular Languages
GATE CS 2012MCQ2 marksMedium (estimate)
GATE CS 2012, Q.46 (CS Q.46)
Consider 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 st...
Regular Expressions, Finite Automata and Regular Languages · Regular Expressions, Finite Automata and Regular Languages
GATE CS 2011MCQ1 markEasy (estimate)
GATE CS 2011, Q.24 (CS Q.24)
Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$ . (For example, let $P$ be the language represented by the regular expression $p^{*} q^{*}$ ...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2011MCQ2 marksMedium (estimate)
GATE CS 2011, Q.42 (CS Q.42)
Definition of a language $L$ with alphabet ${a}$ is given as following. $L = {a^{nk} ∣ k > 0, and n is a positive integer constant}$ What is the minimu...
Regular Expressions, Finite Automata and Regular Languages
GATE CS 2011MCQ2 marksMedium (estimate)
GATE CS 2011, Q.45 (CS Q.45)
A deterministic finite automaton (DFA) $D$ with alphabet $Σ = {a, b}$ is given below. Deterministic finite automaton D with start state p, state q, trap state r, and acce...
Regular Expressions, Finite Automata and Regular Languages

Questions

Other topics of Theory of Computation