Context-Free Grammars, Pushdown Automata and CFLs: GATE CS previous year questions (Theory of Computation)

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 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 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 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 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 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 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 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 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 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.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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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.56 (CS Q.46)
A student wrote two context-free grammars $G_{1}$ and $G_{2}$ for generating a single C-like array declaration. The dimension of the array is at least one. For example, int a[1...
Parsing and Syntax Analysis (LL and LR) · Context-Free Grammars, Pushdown Automata and CFLs
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 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 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 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 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 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

Questions

Other topics of Theory of Computation