Theory of Computation: GATE CS previous year questions, 2011 to 2026

Topics

All Theory of Computation questions

GATE CS 2026 Set 1MSQ1 markMedium (estimate)
GATE CS 2026 Set 1, Q.25
Consider the following grammar where $S$ is the start symbol, and $a$ and $b$ are terminal symbols. $S \to a S b S ∣ b S ∣ ϵ$ Which of the following statement...
Context-Free Grammars, Pushdown Automata and CFLs
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 1MSQ2 marksEasy (estimate)
GATE CS 2026 Set 1, Q.51
Let $L_{1}$ and $L_{2}$ be two languages over a finite alphabet, such that $L_{1} \cap L_{2}$ and $L_{2}$ are regular languages. Which of the following statements is/are always true?
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2026 Set 1MSQ2 marksMedium (estimate)
GATE CS 2026 Set 1, Q.52
Consider the following context-free grammar $G$ . $S \to aba A B A bba$ $A \to aa B B A b ∣ b B abaa$ $B \to a B b ∣ ab$ In the above grammar, $S$ is the...
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2026 Set 2MCQ1 markEasy (estimate)
GATE CS 2026 Set 2, Q.13
Which one of the following statements is equivalent to the following assertion? Turing machine $M$ decides the language $L \subseteq {0, 1}^{*}$
Decidability, Reducibility and Undecidability
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 2026 Set 2MSQ2 marksMedium (estimate)
GATE CS 2026 Set 2, Q.48
Let $Σ = {a, b, c, d}$ and let $L = {a^{i} b^{j} c^{k} d^{ℓ} ∣ i, j, k, ℓ \geq 0}$ . Which of the following constraints ensure(s) that the language $L$ is context-free?
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2025 Set 1MCQ1 markEasy (estimate)
GATE CS 2025 Set 1, Q.19
Consider the following context-free grammar $G$ , where $S$ , $A$ , and $B$ are the variables (non-terminals), $a$ and $b$ are the terminal symbols, $S$ is the start variable, and...
Context-Free Grammars, Pushdown Automata and CFLs
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 1MCQ2 marksMedium (estimate)
GATE CS 2025 Set 1, Q.45
Consider the following two languages over the alphabet ${a, b, c}$ , where $m$ and $n$ are natural numbers. $L_{1} = {a^{m} b^{m} c^{m + n} ∣ m, n \geq 1}$ …
Context-Free Grammars, Pushdown Automata and CFLs
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 2MCQ1 markEasy (estimate)
GATE CS 2025 Set 2, Q.24
Which ONE of the following languages is accepted by a deterministic pushdown automaton?
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2025 Set 2MCQ1 markEasy (estimate)
GATE CS 2025 Set 2, Q.25
Let $G_{1}, G_{2}$ be Context Free Grammars (CFGs) and $R$ be a regular expression. For a grammar $G$ , let $L (G)$ denote the language generated by $G$ . Which ONE among the following...
Decidability, Reducibility and Undecidability
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 marksEasy (estimate)
GATE CS 2024 Set 1, Q.59
Let $G = (V, Σ, S, P)$ be a context-free grammar in Chomsky Normal Form with $Σ = {a, b, c}$ and $V$ containing 10 variable symbols including the start symbol $S$ . T...
Context-Free Grammars, Pushdown Automata and CFLs
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 2MSQ2 marksMedium (estimate)
GATE CS 2024 Set 2, Q.52
Consider a context-free grammar $G$ with the following 3 rules. $S \to a S, S \to a S b S, S \to c$ Let $w \in L (G)$ . Let…
Context-Free Grammars, Pushdown Automata and CFLs
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 2023MCQ2 marksMedium (estimate)
GATE CS 2023, Q.39
Consider the context-free grammar $G$ below $S X \to a S b ∣ X \to a X ∣ X b ∣ a ∣ b,$ where $S$ and $X$ are non-ter...
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2023MCQ2 marksMedium (estimate)
GATE CS 2023, Q.40
Consider the pushdown automaton (PDA) P below, which runs on the input alphabet ${a, b}$ , has stack alphabet ${⊥, A}$ , and has three states ${s, p, q}$ , with $s$ being...
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 2022MSQ1 markMedium (estimate)
GATE CS 2022, Q.23
Which of the following statements is/are TRUE?
Decidability, Reducibility and Undecidability · Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2022MSQ2 marksMedium (estimate)
GATE CS 2022, Q.46
Which of the following is/are undecidable?
Decidability, Reducibility and Undecidability
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 2022MSQ2 marksMedium (estimate)
GATE CS 2022, Q.48
Consider the following languages: $L_{1} = {w w ∣ w \in {a, b}^{*}}$ $L_{2} = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$ $L_{3} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$ Which of the followi...
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2021 Set 1MCQ1 markMedium (estimate)
GATE CS 2021 Set 1, Q.11 (CS Q.1)
Suppose that $L_{1}$ is a regular language and $L_{2}$ is a context-free language. Which one of the following languages is NOT necessarily context-free?
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2021 Set 1MSQ1 markMedium (estimate)
GATE CS 2021 Set 1, Q.22 (CS Q.12)
Let $⟨ M ⟩$ denote an encoding of an automaton $M$ . Suppose that $Σ = {0, 1}$ . Which of the following languages is/are NOT recursive?
Decidability, Reducibility and Undecidability
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 1MCQ2 marksMedium (estimate)
GATE CS 2021 Set 1, Q.49 (CS Q.39)
For a Turing machine $M$ , $⟨ M ⟩$ denotes an encoding of $M$ . Consider the following two languages.…
Decidability, Reducibility and Undecidability
GATE CS 2021 Set 1NAT2 marksHard (estimate)
GATE CS 2021 Set 1, Q.61 (CS Q.51)
In a pushdown automaton $P = (Q, Σ, Γ, δ, q_{0}, F)$ , a transition of the form, $(q, Y) \in δ (p, a, X)$ where $p, q \in Q$ , $a \in Σ \cup {ϵ}$ ,...
Context-Free Grammars, Pushdown Automata and CFLs
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 2MSQ1 markMedium (estimate)
GATE CS 2021 Set 2, Q.22 (CS Q.12)
Let $L_{1}$ be a regular language and $L_{2}$ be a context-free language. Which of the following languages is/are context-free?
Context-Free Grammars, Pushdown Automata and CFLs
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 2MCQ2 marksMedium (estimate)
GATE CS 2021 Set 2, Q.46 (CS Q.36)
Consider the following two statements about regular languages: $S_{1}$ : Every infinite regular language contains an undecidable language as a subset. $S_{2}$ : Every finite language...
Decidability, Reducibility and Undecidability
GATE CS 2021 Set 2MSQ2 marksMedium (estimate)
GATE CS 2021 Set 2, Q.51 (CS Q.41)
For a string $w$ , we define $w^{R}$ to be the reverse of $w$ . For example, if $w = 01101$ then $w^{R} = 10110$ . Which of the following languages is/are context-free?
Context-Free Grammars, Pushdown Automata and CFLs
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 2020MCQ1 markMedium (estimate)
GATE CS 2020, Q.20 (CS Q.10)
Consider the language $L = {a^{n} ∣ n \geq 0} \cup {a^{n} b^{n} ∣ n \geq 0}$ and the following statements. I. $L$ is deterministic context-free. II. $L$ is context-free but no...
Context-Free Grammars, Pushdown Automata and CFLs · Parsing and Syntax Analysis (LL and LR)
GATE CS 2020MCQ2 marksMedium (estimate)
GATE CS 2020, Q.36 (CS Q.26)
Which of the following languages are undecidable? Note that $⟨ M ⟩$ indicates encoding of the Turing machine $M$ .…
Decidability, Reducibility and Undecidability
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 2019MCQ2 marksMedium (estimate)
GATE CS 2019, Q.41 (CS Q.31)
Which one of the following languages over $Σ = {a, b}$ is NOT context-free?
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2019MCQ2 marksMedium (estimate)
GATE CS 2019, Q.44 (CS Q.34)
Consider the following sets: $S_{1}$ : Set of all recursively enumerable languages over the alphabet ${0, 1}$ $S_{2}$ : Set of all syntactically valid C programs $S_{3}$ : Set of all l...
Decidability, Reducibility and Undecidability
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 2018MCQ1 markEasy (estimate)
GATE CS 2018, Q.17 (CS Q.7)
The set of all recursively enumerable languages is
Decidability, Reducibility and Undecidability
GATE CS 2018MCQ2 marksMedium (estimate)
GATE CS 2018, Q.45 (CS Q.35)
Consider the following languages: I. ${a^{m} b^{n} c^{p} d^{q} ∣ m + p = n + q, where m, n, p, q \geq 0}$ II.…
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2018MCQ2 marksMedium (estimate)
GATE CS 2018, Q.46 (CS Q.36)
Consider the following problems. $L (G)$ denotes the language generated by a grammar $G$ . $L (M)$ denotes the language accepted by a machine $M$ . (I) For an unrestricted grammar…
Decidability, Reducibility and Undecidability
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 1MCQ1 markMedium (estimate)
GATE CS 2017 Set 1, Q.10 (CS Q.10)
Consider the following context-free grammar over the alphabet $Σ = {a, b, c}$ with $S$ as the start symbol: $S \to ab S c T ∣ ab c T$ $T \to b T ∣ b$ Which one of the...
Context-Free Grammars, Pushdown Automata and CFLs
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.34 (CS Q.34)
If $G$ is a grammar with productions $S \to S a S ∣ a S b ∣ b S a ∣ S S ∣ ϵ$ where $S$ is the start variable, then which one of the following strings is not genera...
Context-Free Grammars, Pushdown Automata and CFLs
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 1MCQ2 marksEasy (estimate)
GATE CS 2017 Set 1, Q.38 (CS Q.38)
Consider the following languages over the alphabet $Σ = {a, b, c}$ . Let $L_{1} = {a^{n} b^{n} c^{m} ∣ m, n \geq 0}$ and $L_{2} = {a^{m} b^{n} c^{n} ∣ m, n \geq 0}$ . Which of the...
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2017 Set 1MCQ2 marksMedium (estimate)
GATE CS 2017 Set 1, Q.39 (CS Q.39)
Let $A$ and $B$ be finite alphabets and let # be a symbol outside both $A$ and $B$ . Let $f$ be a total function from $A^{*}$ to $B^{*}$ . We say $f$ is computable if there exists a T...
Turing Machines and Chomsky Hierarchy
GATE CS 2017 Set 2MCQ1 markEasy (estimate)
GATE CS 2017 Set 2, Q.4 (CS Q.4)
Let $L_{1}, L_{2}$ be any two context-free languages and $R$ be any regular language. Then which of the following is/are CORRECT? I. $L_{1} \cup L_{2}$ is context-free. II.…
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2017 Set 2MCQ1 markEasy (estimate)
GATE CS 2017 Set 2, Q.16 (CS Q.16)
Identify the language generated by the following grammar, where $S$ is the start variable.…
Context-Free Grammars, Pushdown Automata and CFLs
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 2017 Set 2MCQ2 marksMedium (estimate)
GATE CS 2017 Set 2, Q.40 (CS Q.40)
Consider the following languages.…
Context-Free Grammars, Pushdown Automata and CFLs · Turing Machines and Chomsky Hierarchy
GATE CS 2017 Set 2MCQ2 marksEasy (estimate)
GATE CS 2017 Set 2, Q.41 (CS Q.41)
Let $L (R)$ be the language represented by regular expression $R$ . Let $L (G)$ be the language generated by a context free grammar $G$ . Let $L (M)$ be the language accepted by a Tu...
Decidability, Reducibility and Undecidability
GATE CS 2016 Set 1MCQ1 markEasy (estimate)
GATE CS 2016 Set 1, Q.26 (CS Q.16)
Which of the following languages is generated by the given grammar? $S \to a S ∣ b S ∣ ε$
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2016 Set 1MCQ1 markMedium (estimate)
GATE CS 2016 Set 1, Q.27 (CS Q.17)
Which of the following decision problems are undecidable? I. Given NFAs $N_{1}$ and $N_{2}$ , is $L (N_{1}) \cap L (N_{2}) = \emptyset$ ? II. Given a CFG $G = (N, Σ, P, S)$ and a strin...
Decidability, Reducibility and Undecidability
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 1MCQ2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.52 (CS Q.42)
Consider the following context-free grammars: $G_{1} : S \to a S ∣ B, B \to b ∣ b B$ …
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2016 Set 1MCQ2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.53 (CS Q.43)
Consider the transition diagram of a PDA given below with input alphabet $Σ = {a, b}$ and stack alphabet $Γ = {X, Z}$ . $Z$ is the initial stack symbol. Let $L$ den...
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2016 Set 1MCQ2 marksMedium (estimate)
GATE CS 2016 Set 1, Q.54 (CS Q.44)
Let $X$ be a recursive language and $Y$ be a recursively enumerable but not recursive language. Let $W$ and $Z$ be two languages such that $Y$ reduces to $W$ , and $Z$ ...
Decidability, Reducibility and Undecidability
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 2016 Set 2MCQ2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.53 (CS Q.43)
Consider the following languages: $L_{1} = {a^{n} b^{m} c^{n + m} ∣ m, n \geq 1}$ $L_{2} = {a^{n} b^{n} c^{2 n} ∣ n \geq 1}$ Which one of the following is TRUE?
Context-Free Grammars, Pushdown Automata and CFLs
GATE CS 2016 Set 2MCQ2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.54 (CS Q.44)
Consider the following languages. $L_{1} = {⟨ M ⟩ ∣ M takes at least 2016 steps on some input}$ …
Decidability, Reducibility and Undecidability · Turing Machines and Chomsky Hierarchy
GATE CS 2015 Set 1MCQ1 markMedium (estimate)
GATE CS 2015 Set 1, Q.13 (CS Q.3)
For any two languages $L_{1}$ and $L_{2}$ such that $L_{1}$ is context-free and $L_{2}$ is recursively enumerable but not recursive, which of the following is/are necessarily true? I.…
Decidability, Reducibility and Undecidability
GATE CS 2015 Set 1MCQ2 marksMedium (estimate)
GATE CS 2015 Set 1, Q.61 (CS Q.51)
Consider the NPDA $(Q = {q_{0}, q_{1}, q_{2}}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q_{0}, ⊥, F = {q_{2}})$ , where (as per usual convention) $Q$ is the set of states...
Context-Free Grammars, Pushdown Automata and CFLs
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 2MCQ1 markMedium (estimate)
GATE CS 2015 Set 2, Q.31 (CS Q.21)
Consider the following statements: I. The complement of every Turing decidable language is Turing decidable. II. There exists some language which is in NP but is not Turing deci...
Decidability, Reducibility and Undecidability
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 2015 Set 3MCQ2 marksMedium (estimate)
GATE CS 2015 Set 3, Q.42 (CS Q.32)
Which of the following languages are context-free?…
Context-Free Grammars, Pushdown Automata and CFLs
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 marksEasy (estimate)
GATE CS 2014 Set 1, Q.45 (CS Q.35)
Let $L$ be a language and $L ˉ$ be its complement. Which one of the following is NOT a viable possibility?
Decidability, Reducibility and Undecidability
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 1MCQ2 marksMedium (estimate)
GATE CS 2014 Set 1, Q.48 (CS Q.38)
Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correc...
Turing Machines and Chomsky Hierarchy
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 2MCQ1 markMedium (estimate)
GATE CS 2014 Set 2, Q.26 (CS Q.16)
Let $A \leq_{m} B$ denotes that language $A$ is mapping reducible (also known as many-to-one reducible) to language $B$ . Which one of the following is FALSE?
Decidability, Reducibility and Undecidability
GATE CS 2014 Set 2MCQ2 marksMedium (estimate)
GATE CS 2014 Set 2, Q.45 (CS Q.35)
Let $⟨ M ⟩$ be the encoding of a Turing machine as a string over $Σ = {0, 1}$ . Let…
Decidability, Reducibility and Undecidability
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 2014 Set 3MCQ1 markEasy (estimate)
GATE CS 2014 Set 3, Q.26 (CS Q.16)
Let $Σ$ be a finite non-empty alphabet and let $2^{Σ^{*}}$ be the power set of $Σ^{*}$ . Which one of the following is TRUE?
Decidability, Reducibility and Undecidability
GATE CS 2014 Set 3MCQ2 marksEasy (estimate)
GATE CS 2014 Set 3, Q.45 (CS Q.35)
Which one of the following problems is undecidable?
Decidability, Reducibility and Undecidability
GATE CS 2014 Set 3MCQ2 marksMedium (estimate)
GATE CS 2014 Set 3, Q.46 (CS Q.36)
Consider the following languages over the alphabet $Σ = {0, 1, c}$ : $L_{1} = {0^{n} 1^{n} ∣ n \geq 0}$ $L_{2} = {w c w^{r} ∣ w \in {0, 1}^{*}}$ …
Context-Free Grammars, Pushdown Automata and CFLs
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 2013MCQ1 markEasy (estimate)
GATE CS 2013, Q.17 (CS Q.17)
Which of the following statements is/are FALSE? 1. For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine. 2. Turing recognizable la...
Turing Machines and Chomsky Hierarchy
GATE CS 2013MCQ1 markEasy (estimate)
GATE CS 2013, Q.18 (CS Q.18)
Which of the following statements are TRUE? 1. The problem of determining whether there exists a cycle in an undirected graph is in P. 2. The problem of determining whether ther...
Turing Machines and Chomsky Hierarchy
GATE CS 2013MCQ2 marksMedium (estimate)
GATE CS 2013, Q.32 (CS Q.32)
Consider the following languages. $L_{1} = {0^{p} 1^{q} 0^{r} ∣ p, q, r \geq 0}$ $L_{2} = {0^{p} 1^{q} 0^{r} ∣ p, q, r \geq 0, p \neq = r}$ Which one of the following statements is FALSE?
Context-Free Grammars, Pushdown Automata and CFLs
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 2013MCQ2 marksEasy (estimate)
GATE CS 2013, Q.41 (CS Q.41)
Which of the following is/are undecidable? 1. $G$ is a CFG. Is $L (G) = Φ$ ? 2. $G$ is a CFG. Is $L (G) = Σ^{*}$ ? 3. $M$ is a Turing machine. Is $L (M)$ regular? 4. $A$ is a D...
Decidability, Reducibility and Undecidability
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.8 (CS Q.8)
Which of the following pairs have DIFFERENT expressive power?
Context-Free Grammars, Pushdown Automata and CFLs
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 marksEasy (estimate)
GATE CS 2011, Q.26 (CS Q.26)
Consider the languages $L_{1}$ , $L_{2}$ and $L_{3}$ as given below. $L_{1} = {0^{p} 1^{q} ∣ p, q \in N}$ $L_{2} = {0^{p} 1^{q} ∣ p, q \in N and p = q}$ …
Context-Free Grammars, Pushdown Automata and CFLs
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