chapter

Context-Free Grammars and Pushdown Automata PYQs for GATE CS

Solve 10+ Context-Free Grammars and Pushdown Automata previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

2026 Slot Set2 PYQ

Level 3: Exam Standard

Which of the following grammars is/are ambiguous?

Question 2

2026 Slot Set1 PYQ

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 start symbol, a and b are terminal symbols, and A and B are non-terminal symbols. Let L (G) be the language generated by the grammar G . For a string s \in L (G), let n_{1} (s) be the number of a ’s in s and n_{2} (s) be the number of b ’s in s . Which of the following statements is/are true?

Question 3

2026 Slot Set1 PYQ

Level 3: Exam Standard

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 statements is/are true?

Question 4

2025 Slot Set2 PYQ

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

Question 5

2025 Slot Set1 PYQ

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 the rules of G are described as: S \to aa B ∣ A bb A \to a ∣ a A B \to b ∣ b B Which ONE of the languages L (G) is accepted by G ?

Question 6

2024 Slot Set2 PYQ

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 n_{a} (w), n_{b} (w), n_{c} (w) denote the number of times a, b, c occur in w, respectively. Which of the following statements is/are TRUE?

Question 7

2024 Slot Set1 PYQ

Level 3: Exam Standard

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 . The string w = a^{30} b^{30} c^{30} is derivable from S . The number of steps (application of rules) in the derivation S \to^{*} w is _________

Question 8

2023 PYQ

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 the start state. A transition from state u to state v, labelled c / X / γ, where c is an input symbol or ϵ, X is a stack symbol, and γ is a string of stack symbols, represents the fact that in state u, the PDA can read c from the input, with X on the top of its stack, pop X from the stack, push in the string γ on the stack, and go to state v . In the initial configuration, the stack has only the symbol ⊥ in it. The PDA accepts by empty stack. s p q a/⊥/A⊥ a/A/AA b/A/ε b/A/ε ε/A/ε ε/A/ε ε/A/ε ε/⊥/ε Which one of the following options correctly describes the language accepted by P ?

Question 9

2023 PYQ

Level 3: Exam Standard

Consider the context-free grammar G below S \to a S b ∣ X X \to a X ∣ X b ∣ a ∣ b, where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S . Which one of the following statements is CORRECT?

Question 10

2021 Slot Set1 PYQ

Level 3: Exam Standard

In a pushdown automaton P = (Q, Σ, Γ, δ, q_{0}, F), a transition of the form, p q a, X \to Y where p, q \in Q, a \in Σ \cup {ϵ}, and X, Y \in Γ \cup {ϵ}, represents (q, Y) \in δ (p, a, X) . Consider the following pushdown automaton over the input alphabet Σ = {a, b} and stack alphabet Γ = {#, A} . start q₀ q₁ q₂ q₃ ε, ε \to # ε, ε \to ε ε, A \to A a, ε \to A b, A \to ε The number of strings of length 100 accepted by the above pushdown automaton is __________.

Free preview ends here

Login to view the complete previous-year questions and solutions

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Context-Free Grammars and Pushdown Automata PYQs for GATE CS

Solve 10+ Context-Free Grammars and Pushdown Automata previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Context-Free Grammars and Pushdown Automata

Chapter Journey

1. CFG Language Generation and Symbol-Count Properties

Master deriving strings, tracking terminal counts, and finding invariants in production rules.

High Priority

2. Chomsky Normal Form and Derivation Length

Standardize grammars to bound derivation steps and prove properties about string length.

Support Concept

3. Grammar Ambiguity and Multiple Derivations

Identify when a single string has multiple leftmost derivations or parse trees.

Moderate Priority

4. Pushdown Automata, Transitions and Accepted Languages

Design stack-based machines to recognize context-free languages and match them to grammars.

High Priority

CFG Language Generation and Symbol-Count Properties

Context-Free Grammars and Pushdown Automata › Topic 1

CFG Language Generation and Symbol-Count Properties

Learn to read a grammar as a system of mathematical equations to predict exact symbol counts and language boundaries.

Derivation Trees Symbol Invariants Recursive Unrolling

Translate production rules into algebraic equations for terminal counts.
Identify global invariants that hold for all generated strings.
Unroll recursive rules to determine the exact structure of the generated language.
Avoid the hidden dependency trap when analyzing complex, multi-variable grammars.

Context-Free Grammars and Pushdown Automata: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Theory of Computation · 2026_Set2 MSQ

Which of the following grammars is/are ambiguous?

A.
$S \to a S b ∣ ϵ$
B.
$E \to E + E ∣ E * E ∣ i d$
C.
$S \to a S ∣ S a ∣ ϵ$
D.
$S \to a S ∣ ϵ$

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a grammar ambiguity identification question. We need to check each grammar to see if any string has multiple distinct derivations.

Step 1: Check Grammar A: S → aSb | ε

This generates {a^n b^n | n ≥ 0}.

For any string a^n b^n, there's only ONE way to derive it:

Must apply S → aSb exactly n times
Then apply S → ε once
Order is forced (always leftmost or always rightmost)

Grammar A is UNAMBIGUOUS.

Step 2: Check Grammar B: E → E+E | E*E | id

This is the classic expression grammar.

For string "id+id*id":

Derivation 1: E ⇒ E+E ⇒ id+E ⇒ id+EE ⇒ id+idE ⇒ id+idid (groups as id + (id id))

Derivation 2: E ⇒ EE ⇒ E+EE ⇒ id+EE ⇒ id+idE ⇒ id+idid (groups as (id + id) id)

Two different parse trees ⇒ Grammar B is AMBIGUOUS.

Step 3: Check Grammar C: S → aS | Sa | ε

For string "aa":

Derivation 1: S ⇒ aS ⇒ aaS ⇒ aa (using S → aS twice, then S → ε)

Derivation 2: S ⇒ Sa ⇒ aSa ⇒ aa (using S → Sa, then S → aS for the first S, then S → ε)

These are two distinct leftmost derivations for "aa".

Grammar C is AMBIGUOUS.

Step 4: Check Grammar D: S → aS | ε

This generates a* (any number of a's).

For string "aaa", there is only one leftmost derivation:

S ⇒ aS ⇒ aaS ⇒ aaaS ⇒ aaa

Grammar D is UNAMBIGUOUS.

Answer: Grammars B and C are ambiguous.

Question 2 · Theory of Computation · 2026_Set1 MSQ

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 start symbol,

a

and

b

are terminal symbols, and

A

and

B

are non-terminal symbols.

Let

L (G)

be the language generated by the grammar

G

. For a string

s \in L (G)

, let

n_{1} (s)

be the number of

a

’s in

s

and

n_{2} (s)

be the number of

b

’s in

s

.

Which of the following statements is/are true?

A.
There is a string $s \in L (G)$ such that $n_{1} (s) < n_{2} (s)$
B.
For every string $s \in L (G)$ , $n_{1} (s) \geq n_{2} (s)$
C.
There is a string $s \in L (G)$ such that $n_{1} (s) > 2 n_{2} (s)$
D.
For every string $s \in L (G)$ , $n_{1} (s) \leq 2 n_{2} (s)$

Question 3 · Theory of Computation · 2026_Set1 MSQ

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 statements is/are true?

A.
The grammar is ambiguous
B.
The string $abb$ has two distinct derivations in this grammar
C.
The string $abab$ has only one rightmost derivation
D.
The language generated by the grammar is undecidable

Correct Answer:

["A","B"]

Step-by-Step Solution

Key idea: This is a grammar ambiguity question. To prove a grammar is ambiguous, we must find at least one string with multiple distinct leftmost derivations.

Step 1: Check string "abb".

Derivation 1 (Leftmost):

S ⇒ aSbS

⇒ abSbS (using S → bS for the first S)

⇒ abbS (using S → ε for the second S)

⇒ abb (using S → ε for the third S)

Derivation 2 (Leftmost):

S ⇒ aSbS

⇒ abS (using S → ε for the first S)

⇒ abbS (using S → bS for the remaining S)

⇒ abb (using S → ε for the remaining S)

These are two distinct leftmost derivations for "abb", so the grammar is ambiguous.

Step 2: Evaluate options.

A: True (proven above).

B: True (proven above).

C: False. The string "abab" has multiple rightmost derivations. For example:

RMD 1: S ⇒ aSbS ⇒ aSbaSbS ⇒ aSbaSb ⇒ aSbab ⇒ abab

RMD 2: S ⇒ aSbS ⇒ aSb ⇒ a(aSbS)b ⇒ a(aSb)b ⇒ a(ab)b ⇒ abab

D: False. All context-free languages are decidable (e.g., via CYK algorithm).

Answer: Options A and B are true.

Question 4 · Theory of Computation · 2025_Set2 MCQ

Which ONE of the following languages is accepted by a deterministic pushdown automaton?

A.
Any regular language.
B.
Any context-free language.
C.
Any language accepted by a non-deterministic pushdown automaton.
D.
Any decidable language.

Question 5 · Theory of Computation · 2025_Set1 MCQ

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 the rules of

G

are described as:

S \to aa B ∣ A bb

A \to a ∣ a A

B \to b ∣ b B

Which ONE of the languages

L (G)

is accepted by

G

A.
$L (G) = {a^{2} b^{n} ∣ n \geq 1} \cup {a^{n} b^{2} ∣ n \geq 1}$
B.
$L (G) = {a^{n} b^{2 n} ∣ n \geq 1} \cup {a^{2 n} b^{n} ∣ n \geq 1}$
C.
$L (G) = {a^{n} b^{n} ∣ n \geq 1}$
D.
$L (G) = {a^{2 n} b^{2 n} ∣ n \geq 1}$

Question 6 · Theory of Computation · 2024_Set2 MSQ

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 $n_{a} (w)$ , $n_{b} (w)$ , $n_{c} (w)$ denote the number of times $a, b, c$ occur in $w$ , respectively. Which of the following statements is/are TRUE?

A.
$n_{a} (w) > n_{b} (w)$
B.
$n_{a} (w) > n_{c} (w) - 2$
C.
$n_{c} (w) = n_{b} (w) + 1$
D.
$n_{c} (w) = n_{b} (w) * 2$

Question 7 · Theory of Computation · 2024_Set1 NAT

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$ . The string $w = a^{30} b^{30} c^{30}$ is derivable from $S$ . The number of steps (application of rules) in the derivation $S \to^{*} w$ is _________

Correct Answer:

179

Step-by-Step Solution

Key idea: This is a Chomsky Normal Form derivation length question. In CNF, there's a direct formula relating string length to the number of derivation steps.

Step 1: Recall the CNF derivation length theorem.

For a grammar in Chomsky Normal Form (CNF):

If a string w has length n (where n ≥ 1)
Then any derivation of w requires exactly 2n - 1 steps

Step 2: Calculate the length of the given string.

w = a^30 b^30 c^30

Length n = 30 + 30 + 30 = 90

Step 3: Apply the formula.

Number of steps = 2n - 1

Number of steps = 2(90) - 1

Number of steps = 180 - 1 = 179

Step 4: Verify understanding.

Why does this formula work?

In CNF, each production is either A → BC (2 non-terminals) or A → a (1 terminal)
To generate n terminals, we need:
(n - 1) productions of type A → BC to build the structure
n productions of type A → a to generate terminals
Total: (n - 1) + n = 2n - 1 steps

Note: The number of variables (10) is irrelevant - it's a distractor!

Answer: 179

Question 8 · Theory of Computation · 2023 MCQ

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 the start state. A transition from state

u

to state

v

, labelled

c / X / γ

, where

c

is an input symbol or

ϵ

X

is a stack symbol, and

γ

is a string of stack symbols, represents the fact that in state

u

, the PDA can read

c

from the input, with

X

on the top of its stack, pop

X

from the stack, push in the string

γ

on the stack, and go to state

v

. In the initial configuration, the stack has only the symbol

⊥

in it. The PDA accepts by empty stack.

Which one of the following options correctly describes the language accepted by

P

A.
$\{a^mb^n\mid 1\leq m\text{ and }n<m\}$
B.
${a^{m} b^{n} ∣ 0 \leq n \leq m}$
C.
${a^{m} b^{n} ∣ 0 \leq m and 0 \leq n}$
D.
${a^{m} ∣ 0 \leq m} \cup {b^{n} ∣ 0 \leq n}$

Question 9 · Theory of Computation · 2023 MCQ

Consider the context-free grammar

G

below

S \to a S b ∣ X

X \to a X ∣ X b ∣ a ∣ b,

where

S

and

X

are non-terminals, and

a

and

b

are terminal symbols. The starting non-terminal is

S

.

Which one of the following statements is CORRECT?

A.
The language generated by $G$ is $(a + b)^{*}$
B.
The language generated by $G$ is $a^{*} (a + b) b^{*}$
C.
The language generated by $G$ is $a^{*} b^{*} (a + b)$
D.
The language generated by $G$ is not a regular language

Correct Answer:

Step-by-Step Solution

Key idea: This is a CFG language identification question. We need to analyze what strings the grammar can generate by understanding the role of each non-terminal.

Step 1: Analyze the grammar structure.

Grammar:

S → aSb | X

X → aX | Xb | a | b

Step 2: Understand what X generates.

X can produce 'a' or 'b' directly.

Recursive rules X → aX and X → Xb allow adding 'a' to the left or 'b' to the right.

This means X can never generate a 'b' followed by an 'a'.

Thus, L(X) = { a^i b^j | i + j >= 1 } = ab - {ε}.

Step 3: Understand what S generates.

S → X allows S to produce anything X produces.

S → aSb wraps matching pairs of 'a' and 'b' around whatever S produces.

So S generates a^n w b^n, where w ∈ L(X) and n >= 0.

Let w = a^i b^j (with i + j >= 1).

Then the string is a^n a^i b^j b^n = a^{n+i} b^{j+n}.

Let N = n + i and M = j + n.

Since i + j >= 1, we have N + M = 2n + i + j >= 1.

Also, N >= 0 and M >= 0.

Thus, S generates exactly { a^N b^M | N + M >= 1 } = ab - {ε}.

Step 4: Match with options.

Option A: (a+b)* includes "ba" and ε, which are not in L(S).

Option B: a(a+b)b generates strings with zero or more 'a's, exactly one 'a' or 'b', and zero or more 'b's. This is exactly (a^+ b) ∪ (a b^+) = ab - {ε}. This matches L(S).

Option C: ab(a+b) can generate "ba" (e.g., a^0 b^1 a), which is not in L(S).

Option D: The language is regular, so this is false.

Answer: Option B is correct.

Question 10 · Theory of Computation · 2021_Set1 NAT

In a pushdown automaton

P = (Q, Σ, Γ, δ, q_{0}, F)

, a transition of the form,

where

p, q \in Q

a \in Σ \cup {ϵ}

, and

X, Y \in Γ \cup {ϵ}

, represents

(q, Y) \in δ (p, a, X) .

Consider the following pushdown automaton over the input alphabet

Σ = {a, b}

and stack alphabet

Γ = {#, A}

.

The number of strings of length 100 accepted by the above pushdown automaton is __________.

Correct Answer:

Step-by-Step Solution

Key idea: This is a PDA language analysis question. We need to trace the PDA transitions to understand the accepted language, then count valid strings of length 100.

Step 1: Analyze transitions.

q0 → q1: ε, ε → # (pushes bottom marker)
q1 → q1: a, ε → A (pushes A for each 'a')
q1 → q2: ε, ε → ε (moves to popping state)
q2 → q2: b, A → ε (pops A for each 'b')
q2 → q3: ε, A → A (moves to final state if A is on top)

Step 2: Determine accepted language.

To reach the final state q3, the PDA must be in q2 with 'A' on top of the stack.

This means the number of 'A's pushed (n) must be strictly greater than the number of 'A's popped (m).

So, n > m.

The input string must be of the form a^n b^m, where n > m >= 0.

Step 3: Count strings of length 100.

We need n + m = 100 and n > m >= 0.

Substitute m = 100 - n:

n > 100 - n => 2n > 100 => n > 50.

Since n <= 100 (because m >= 0), the possible values for n are 51, 52, ..., 100.

The number of such values is 100 - 51 + 1 = 50.

Answer: 50

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Context-Free Grammars and Pushdown Automata PYQs for GATE CS

Chapter Roadmap: Context-Free Grammars and Pushdown Automata

Chapter Journey

CFG Language Generation and Symbol-Count Properties

CFG Language Generation and Symbol-Count Properties

Context-Free Grammars and Pushdown Automata: Solved Questions with Step-by-Step Explanations (10 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit