GATE CS

Context-free grammars and push-down automata

A context-free grammar generates strings by rewriting variables, and a push-down automaton (a finite automaton with a stack) accepts exactly the same languages. These notes cover derivations and parse trees, ambiguity, simplification and normal forms, the $2 n - 1$ step count in Chomsky normal form, designing and tracing a PDA, conversions between grammars and PDAs, and which languages need non-determinism.

9 previous-year questions · 8 solved · 5 practice questions

Context-free grammars and derivations

A context-free grammar (CFG) is a 4-tuple $G = (V, Σ, P, S)$ : $V$ is the finite set of variables (non-terminals), $Σ$ the terminals (the input alphabet), $P$ the productions and $S \in V$ the start variable. Every production has the form $A \to α$ with $A \in V$ and $α \in (V \cup Σ)^{*}$ , so the left side is always a single variable. Convention: $ε$ is the empty string, $∣ w ∣$ is the length of $w$ , and $L (G) = {w \in Σ^{*} ∣ S \Rightarrow^{*} w}$ .

A derivation step $α A β \Rightarrow α γ β$ replaces one variable using one production $A \to γ$ . In a leftmost derivation the leftmost variable is replaced at every step; in a rightmost derivation the rightmost one. A string of variables and terminals reached from $S$ is a sentential form; if it has only terminals it is a sentence of $L (G)$ .

Grammar	Language generated
$S \to a S b ∣ ε$	${a^{n} b^{n} ∣ n \geq 0}$
$S \to a S b ∣ ab$	${a^{n} b^{n} ∣ n \geq 1}$
$S \to a S a ∣ b S b ∣ ε$	${w w^{R} ∣ w \in {a, b}^{*}}$ (even-length palindromes)
$S \to a S a ∣ b S b ∣ a ∣ b ∣ ε$	all palindromes over ${a, b}$
$S \to S S ∣ (S) ∣ ε$	balanced parentheses
$S \to a S b ∣ a S bb ∣ ε$	${a^{i} b^{j} ∣ i \leq j \leq 2 i}$

Finding the language of a grammar

List the shortest strings derivable and look for the pattern.
Name what each variable generates on its own (for example $A \to a A ∣ a$ gives $a^{+}$ ).
Combine the pieces following the right-hand sides, then test the guess on two or three strings.
Check the boundary case: whether $ε$ is generated.

EXAM TIP

A language is context-free if some CFG generates it. Every regular language is context-free, but not conversely: ${a^{n} b^{n} ∣ n \geq 0}$ is context-free and not regular. A grammar in which every production has the form $A \to x B$ or $A \to x$ (with $x \in Σ^{*}$ ) is right-linear and generates a regular language; for example $S \to a S ∣ b$ generates $a^{*} b$ .

Parse trees and ambiguity

A parse tree has the start variable at the root, each internal node labelled by a variable whose children are the symbols on the right side of the production used, and leaves labelled by terminals, or by $ε$ when $ε$ is the only child (the production $A \to ε$ ). The yield is the leaves read left to right. A terminal string $w$ is the yield of some parse tree with root $S$ exactly when $S \Rightarrow^{*} w$ .

Many derivations can give the same tree (they differ only in the order of replacement), but each parse tree has exactly one leftmost derivation and exactly one rightmost derivation. So for a string $w$ : number of parse trees = number of leftmost derivations = number of rightmost derivations.

A grammar is ambiguous if some string in $L (G)$ has two or more different parse trees (equivalently two leftmost derivations, or two rightmost derivations). To show a grammar ambiguous, exhibit one string with two different parse trees. A language is inherently ambiguous if every grammar generating it is ambiguous, for example ${a^{i} b^{j} c^{k} ∣ i, j, k \geq 0, i = j or j = k}$ .

WORKED EXAMPLE

Show that $S \to S S ∣ a$ is ambiguous and count the parse trees of $aaa$ .

Solution

The only productions are $S \to S S$ and $S \to a$ , so every tree for $aaa$ has the root $S \to S S$ .
Tree 1: the left child splits again, giving $(aa) a$ : $S \Rightarrow S S \Rightarrow S S S \Rightarrow a S S \Rightarrow aa S \Rightarrow aaa$ .
Tree 2: the right child splits again, giving $a (aa)$ : $S \Rightarrow S S \Rightarrow a S \Rightarrow a S S \Rightarrow aa S \Rightarrow aaa$ .
There are no others: the root's two children must yield $a$ and $aa$ , or $aa$ and $a$ , and $aa$ has exactly one tree ( $S \to S S$ , each child $S \to a$ ).
The two trees differ, so $aaa$ has two leftmost derivations and the grammar is ambiguous.

Answer: Ambiguous; $aaa$ has exactly 2 parse trees.

EXAM TIP

Ambiguity is a property of a grammar; a language is inherently ambiguous only when every grammar for it is ambiguous. Rewriting a grammar can often remove ambiguity: $E \to E + E ∣ a$ generates the same language as the unambiguous $E \to E + a ∣ a$ , and the dangling-else grammar can be rewritten to fix which if each else belongs to. No algorithm decides whether an arbitrary CFG is ambiguous.

Simplifying grammars

Simplification removes $ε$ -productions, unit productions ( $A \to B$ ) and useless symbols without changing the language, except that $ε$ is handled separately. Apply the steps in this order: $ε$ -productions, then unit productions, then useless symbols (non-generating first, then unreachable). Removing $ε$ -productions can create unit productions and useless symbols, and removing unit productions can leave useless symbols, so another order can leave work undone.

Procedure

Nullable variables: $A$ is nullable if $A \Rightarrow^{*} ε$ . Start with variables having $A \to ε$ ; add $B$ if some $B \to X_{1} \dots X_{k}$ has every $X_{i}$ already nullable.
Remove $ε$ -productions: replace each production $A \to α$ by every version obtained by deleting any subset of the nullable symbols in $α$ ; drop every $A \to ε$ and never create one. The new grammar generates $L - {ε}$ ; if $ε \in L$ , add a new start variable $S^{'}$ with $S^{'} \to S ∣ ε$ .
Unit productions $A \to B$ : find every unit pair $(A, B)$ with $A \Rightarrow^{*} B$ using unit productions only (including $(A, A)$ and pairs reached through a chain); for each pair, give $A$ every non-unit production of $B$ ; then delete all unit productions.
Non-generating variables: keep those that can derive a terminal string (start with variables having a terminal-only right side and grow). Delete the others and every production using them.
Unreachable variables: keep those reachable from $S$ in the dependency graph. Delete the others. Do this after the generating test.

WORKED EXAMPLE

Simplify $S \to a A b ∣ B$ , $A \to a A ∣ ε$ , $B \to C$ , $C \to c ∣ D$ , $D \to d D$ .

Solution

Nullable: only $A$ . Remove $ε$ -productions: $S \to a A b ∣ ab ∣ B$ and $A \to a A ∣ a$ .
Unit pairs (besides $(X, X)$ ): $(S, B)$ , $(S, C)$ , $(S, D)$ , $(B, C)$ , $(B, D)$ , $(C, D)$ . Replace: $S \to a A b ∣ ab ∣ c ∣ d D$ , $B \to c ∣ d D$ , $C \to c ∣ d D$ , $D \to d D$ .
Generating variables: $S$ (through $c$ ), $A$ (through $a$ ), $B$ , $C$ . $D$ is non-generating (it only produces $d D$ ), so remove it and every rule using it: $S \to a A b ∣ ab ∣ c$ , $A \to a A ∣ a$ , $B \to c$ , $C \to c$ .
Reachable from $S$ : $S$ and $A$ only; $B$ and $C$ are unreachable and are removed.

Answer: $S \to a A b ∣ ab ∣ c$ , $A \to a A ∣ a$ , generating ${a^{m} b ∣ m \geq 1} \cup {c}$ .

Normal forms (CNF and GNF)

Chomsky normal form (CNF): every production is $A \to B C$ (two variables) or $A \to a$ (one terminal), with the extra rule $S \to ε$ allowed only when $ε \in L$ and $S$ never appears on a right side. For every CFL $L$ , the language $L - {ε}$ has a CNF grammar.

Converting to CNF

Simplify first: remove $ε$ -productions, unit productions and useless symbols.
For each terminal $a$ in a right side of length 2 or more, add a variable $C_{a} \to a$ and use $C_{a}$ instead of $a$ .
Break right sides longer than 2: $A \to B_{1} B_{2} \dots B_{k}$ becomes $A \to B_{1} D_{1}$ , $D_{1} \to B_{2} D_{2}$ , $\dots$ , $D_{k - 2} \to B_{k - 1} B_{k}$ .

DERIVATION LENGTH IN CHOMSKY NORMAL FORM

steps to derive w in CNF = 2∣ w ∣ - 1

For $∣ w ∣ = n \geq 1$ and any derivation of $w$ from $S$ in a CNF grammar: $n - 1$ steps use $A \to B C$ and $n$ steps use $A \to a$ . In the parse tree there are $n - 1$ variable nodes with two variable children and $n$ variable nodes whose only child is a terminal leaf, so $2 n - 1$ variable nodes, one per step.

Greibach normal form (GNF): every production is $A \to a α$ with $a$ a terminal and $α \in V^{*}$ (possibly empty). For every CFL $L$ , the language $L - {ε}$ has a GNF grammar. Every step adds exactly one terminal, so any derivation of a string of length $n$ takes exactly $n$ steps. From a GNF grammar one can build a one-state PDA with no $ε$ -moves: start with $S$ on the stack and, for each $A \to a α$ , add $δ (q, a, A) ∋ (q, α)$ ; it accepts by empty stack.

DERIVATION LENGTH IN GREIBACH NORMAL FORM

steps to derive w in GNF = ∣ w ∣

For $∣ w ∣ = n \geq 1$ ; each step adds exactly one terminal.

EXAM TIP

Check the conditions before using a count: $2 n - 1$ needs a CNF grammar and $n \geq 1$ . In an arbitrary grammar the length of a derivation of a string of length $n$ is not fixed.

Push-down automata

A push-down automaton (PDA) is a finite automaton with an unbounded stack. Formally $P = (Q, Σ, Γ, δ, q_{0}, Z_{0}, F)$ : states $Q$ , input alphabet $Σ$ , stack alphabet $Γ$ , start state $q_{0}$ , initial stack symbol $Z_{0}$ and accepting states $F$ . The transition function is $δ : Q \times (Σ \cup {ε}) \times Γ \to$ finite subsets of $Q \times Γ^{*}$ . A move $δ (q, a, X) ∋ (p, γ)$ reads $a$ (or nothing when $a = ε$ ), pops $X$ , pushes the string $γ$ (leftmost symbol on top) and goes to $p$ . A configuration (instantaneous description) is written $(q, x, γ)$ : current state, input still unread, stack contents with the top on the left; the move above takes $(q, a x, X β)$ to $(p, x, γ β)$ .

Acceptance mode	Input $w$ is accepted if
Final state	after reading all of $w$ some computation can be in a state of $F$ (stack contents do not matter)
Empty stack	after reading all of $w$ some computation can have an empty stack (the set $F$ is not used)

For non-deterministic PDAs the two modes accept exactly the same class of languages, and each can be converted to the other. A PDA is deterministic (DPDA) if for each $(q, a, X)$ there is at most one move, and if $δ (q, ε, X)$ is non-empty then $δ (q, a, X)$ is empty for every $a \in Σ$ . A DPDA may still have $ε$ -moves; the rule only forbids a choice between an $ε$ -move and an input move. Convention in these notes: a missing transition means that computation halts and rejects.

State	Input	Top of stack	Move
→ $q_{0}$	$a$	$Z_{0}$	stay in $q_{0}$ , replace $Z_{0}$ by $A Z_{0}$ (push $A$ )
$q_{0}$	$a$	$A$	stay in $q_{0}$ , replace $A$ by $AA$ (push $A$ )
$q_{0}$	$b$	$A$	go to $q_{1}$ , pop
$q_{1}$	$b$	$A$	stay in $q_{1}$ , pop
$q_{1}$	$ε$	$Z_{0}$	go to $q_{2}$ , leave $Z_{0}$
$q_{2}$	—	—	no moves (accepting)

The table is a DPDA for ${a^{n} b^{n} ∣ n \geq 1}$ by final state: push one $A$ per $a$ , pop one per $b$ , and accept when the stack is back to $Z_{0}$ . Traces: $ab$ ends in $q_{2}$ (accepted); $aab$ ends in $q_{1}$ with $A Z_{0}$ (rejected); $abb$ reaches $q_{2}$ with a $b$ unread and halts (rejected); $ε$ stays in $q_{0}$ (rejected). For ${w w^{R}}$ the machine pushes $w$ , then must guess the middle and pop while matching $w^{R}$ . That guess is the non-determinism.

Designing a PDA

Decide what the stack should count or remember (a count of $a$ 's, or the first half of the string).
Use the finite control for the phase of the input (reading $a$ 's, then $b$ 's).
Choose the acceptance mode (empty stack is often the simplest for matching).
Where the middle or the phase change cannot be known in advance, use a non-deterministic $ε$ -move.
Trace the shortest accepted string, one string that is rejected for the wrong count, and $ε$ .

EXAM TIP

${a^{n} b^{2 n} ∣ n \geq 0}$ and ${a^{n} b^{n + 1} ∣ n \geq 0}$ are DCFLs. ${a^{n} b^{n} c^{n} ∣ n \geq 0}$ is not context-free (proved with the pumping lemma for CFLs); the intuition is that one stack cannot compare one count against two others. A PDA with two stacks can simulate a Turing machine, and a PDA whose stack height is bounded by a constant accepts only regular languages.

CFGs, PDAs and determinism

EQUIVALENCE OF CFGS AND PDAS

CFLs = languages accepted by NPDAs

Every CFG has an equivalent NPDA and every NPDA has an equivalent CFG, with either acceptance mode.

CFG to PDA (empty stack)

Use one state $q$ , stack alphabet $V \cup Σ$ , and the start variable $S$ as the initial stack symbol.
For each production $A \to α$ add the move $δ (q, ε, A) ∋ (q, α)$ : pop the variable and push its right side.
For each terminal $a$ add $δ (q, a, a) = {(q, ε)}$ : match the input against the stack top and pop.
The PDA simulates a leftmost derivation: it accepts $w$ by empty stack exactly when $S \Rightarrow^{*} w$ .

PDA to CFG: start from a PDA that accepts by empty stack and pushes at most two symbols per move (any PDA can be converted to such a form). Use variables $[pX q]$ , meaning 'starting in $p$ with $X$ on top, the machine can reach $q$ having popped $X$ and consumed exactly the string generated'. The start variable $S$ has $S \to [q_{0} Z_{0} p]$ for every state $p$ . For a move with input $a \in Σ \cup {ε}$ : $δ (p, a, X) ∋ (r, ε)$ gives $[pX r] \to a$ ; $δ (p, a, X) ∋ (r, Y)$ gives $[pX s] \to a [r Y s]$ for every state $s$ ; $δ (p, a, X) ∋ (r, Y_{1} Y_{2})$ gives $[pX s] \to a [r Y_{1} t] [t Y_{2} s]$ for all states $s, t$ . The grammar has at most $∣ Q ∣^{2} ∣Γ∣ + 1$ variables.

	DPDA	NPDA
Languages accepted	deterministic CFLs (DCFLs)	all CFLs
Final state vs empty stack	final state is more powerful: empty-stack DPDAs accept exactly the DCFLs with the prefix property (no string of the language is a proper prefix of another)	same power
Examples	${a^{n} b^{n}}$ , ${w c w^{R}}$ , ${a^{n} b^{m} ∣ n \neq = m}$ (all DCFLs)	${w w^{R}}$ , palindromes, ${a^{n} b^{n}} \cup {a^{n} b^{2 n}}$ (CFLs that are not DCFLs)
Closed under complement	yes	no
Closed under union, intersection	no for both	union yes, intersection no
Closed under concatenation, Kleene star	no for both	yes for both
Closed under reversal, homomorphism	no for both	yes for both
Closed under intersection with a regular language	yes	yes

Question about CFGs	Decidable?
Membership: is $w \in L (G)$ ?	yes (for example the CYK algorithm on a CNF grammar, $O (∣ w ∣^{3})$ time for a fixed grammar)
Emptiness: is $L (G) = \emptyset$ ?	yes (test whether $S$ is generating)
Finiteness: is $L (G)$ finite?	yes
Is $G$ ambiguous?	no
Is $L (G) = Σ^{*}$ ?	no
Is $L (G_{1}) = L (G_{2})$ ?	no
Is $L (G_{1}) \cap L (G_{2}) = \emptyset$ ?	no
Is $L (G)$ regular?	no

EXAM TIP

Regular $\subset$ DCFL $\subset$ CFL, both inclusions proper. ${w w^{R}}$ and the palindromes are context-free but not deterministic. ${a^{i} b^{j} c^{k} ∣ i = j or j = k}$ is context-free but not deterministic, because it is inherently ambiguous and every DCFL has an unambiguous grammar. The converse fails: a language with an unambiguous grammar need not be a DCFL ( ${w w^{R}}$ has the unambiguous grammar $S \to a S a ∣ b S b ∣ ε$ ).

PREVIOUS-YEAR QUESTIONS

9 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 2026 CS1 Q.25

GATE 2026 · CS1Q.25 · 1 mark · 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

Answer and solution

GATE 2026 CS1 Q.25: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.25: answer and solution

GATE 2026 CS1 Q.52

GATE 2026 · CS1Q.52 · 2 marks · MSQ

Consider the following context-free grammar $G$ .

S A B \to aba A B A bba \to aa B B A b ∣ b B abaa \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)$

Answer and solution

GATE 2026 CS1 Q.52: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS1 Q.52: answer and solution

GATE 2026 CS2 Q.29

GATE 2026 · CS2Q.29 · 1 mark · 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 ∣ ϵ$

Answer and solution

GATE 2026 CS2 Q.29: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.29: answer and solution

GATE 2025 CS1 Q.19

GATE 2025 · CS1Q.19 · 1 mark · 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}$

Official answer

Official answer: ASource: Official answer key, GATE 2025 CS1 (IIT Roorkee)

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.19: official answer

GATE 2025 CS2 Q.24

GATE 2025 · CS2Q.24 · 1 mark · 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.

Answer and solution

GATE 2025 CS2 Q.24: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.24: answer and solution

GATE 2024 CS1 Q.59

GATE 2024 · CS1Q.59 · 2 marks · 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 ______.

Answer and solution

GATE 2024 CS1 Q.59: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.59: answer and solution

GATE 2024 CS2 Q.52

GATE 2024 · CS2Q.52 · 2 marks · 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$

Answer and solution

GATE 2024 CS2 Q.52: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.52: answer and solution

GATE 2023 CS Q.39

GATE 2023 · CSQ.39 · 2 marks · MCQ

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-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

Answer and solution

GATE 2023 CS Q.39: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.39: answer and solution

GATE 2023 CS Q.40

GATE 2023 · CSQ.40 · 2 marks · 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$ ?

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

(A)
${a^{m} b^{n} ∣ 1 \leq m 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}$

Answer and solution

GATE 2023 CS Q.40: answer and solution

OTHER EXAMS

ISRO: 6 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.32

ISRO 2025 · CSQ.32 · 1 mark · MCQ

32. For the same input string, which of the following options is true in the case of ambiguous grammar?
(i) two different parse trees
(ii) two leftmost derivations
(iii) two rightmost derivations
(iv) leftmost and rightmost derivations are different
Which one is correct?

(A)
(i), (ii), (iii) are true; (iv) is false
(B)
(i) is true; (ii), (iii), (iv) are false
(C)
(i), (iv) are true; (ii), (iii) are false
(D)
(i) is false; (ii), (iii), (iv) are true

Answer and solution

ISRO CS 2025 Q.32: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.32: answer and solution

ISRO CS 2025 Q.33

ISRO 2025 · CSQ.33 · 1 mark · MCQ

Which of the following strings will correctly match the Grammar G represented by production rules given?

S → A | B
A → aAb | c
B → bBd | e

(A)
accbb
(B)
aacbb
(C)
abaed
(D)
aaebb

Answer and solution

ISRO CS 2025 Q.33: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.33: answer and solution

ISRO CS 2025 Q.80

ISRO 2025 · CSQ.80 · 1 mark · MCQ

Consider the context-free grammar G below. Here S is the starting non-terminal symbol, while a and b are terminal symbols.
S → a S b | T
T → b T | b
The language generated by G is:

(A)
{a^m b^n : 0 ≤ m < n}
(B)
{a^m b^n : 0 < m < n}
(C)
{a^m b^n : 0 < n ≤ m}
(D)
{a^n b^n : 0 ≤ n}

Answer and solution

ISRO CS 2025 Q.80: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2025 Q.80: answer and solution

ISRO CS 2023 Q.8

ISRO 2023 · CSQ.8 · 1 mark · MCQ

Consider the context-free grammar G below for arithmetic expressions:
E → E + E | E × E | id
Which of the following statements is TRUE:

(A)
The string “id + id × id” has no parse tree according to G
(B)
The string “id + id × id” has only one parse tree according to G
(C)
The string “id + id × id” has exactly two parse trees according to G
(D)
The string “id + id × id” has more than two parse trees according to G

Answer and solution

ISRO CS 2023 Q.8: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.8: answer and solution

ISRO CS 2023 Q.57

ISRO 2023 · CSQ.57 · 1 mark · MCQ

Consider the context-free grammar G below. Here S is the starting non-terminal symbol, while a and b are terminal symbols.

S → aSb | T
T → bT | b

The language generated by G is:

(A)
{a^m b^n : 0 ≤ m < n}
(B)
{a^m b^n : 0 < m < n}
(C)
{a^m b^n : 0 < n ≤ m}
(D)
{a^n b^n : 0 ≤ n}

Answer and solution

ISRO CS 2023 Q.57: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.57: answer and solution

ISRO CS 2023 Q.60

ISRO 2023 · CSQ.60 · 1 mark · MCQ

Consider the context-free grammar G below. Here S is the starting non-terminal symbol, while a and b are terminal symbols.

S → aaSb | T
T → Tb | a

Which of the following statements is true about the language L(G) generated by G?

(A)
aabbaabb belongs to L(G) but aabb does not
(B)
aaaaabbb belongs to L(G) but aaaabb does not
(C)
aaaabb belongs to L(G) but aabbaabb does not
(D)
aaabb belongs to L(G) but aaaaabbb does not

Answer and solution

ISRO CS 2023 Q.60: answer and solution

See the question in the paper

Tap to open full size

ISRO CS 2023 Q.60: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 11 mark · NAT

A grammar in Chomsky normal form generates a string $w$ of length 9. How many derivation steps (applications of a production) does any derivation of $w$ from the start variable take?

Answer and solution

Answer: $17$

In CNF, $n - 1$ steps use $A \to B C$ and $n$ steps use $A \to a$ .
For $n = 9$ this is $8 + 9 = 17$ , that is $2 n - 1 = 17$ .

PRACTICE 21 mark · MCQ

Which of the following languages over ${a, b}$ (with $c$ a separator where shown) is context-free but is NOT accepted by any deterministic push-down automaton?

(A)
${a^{n} b^{n} ∣ n \geq 1}$
(B)
${w c w^{R} ∣ w \in {a, b}^{*}}$
(C)
${w w^{R} ∣ w \in {a, b}^{*}}$
(D)
${a^{n} b^{m} ∣ n \neq = m}$

Answer and solution

Answer: (C)

A is accepted by a DPDA: push for $a$ , pop for $b$ .
B has a marker $c$ showing where the middle is, so a DPDA pushes $w$ , then pops while reading $w^{R}$ .
D is a DCFL: a DPDA pushes one $A$ per $a$ and pops one per $b$ , accepting by final state if $A$ 's remain when the input ends ( $n > m$ ), or if a $b$ is read with $Z_{0}$ on top and only $b$ 's follow ( $m > n$ ).
In C the middle is not marked, so the machine has to guess where $w$ ends; no deterministic machine can do this. Answer C.

PRACTICE 32 marks · MSQ

Consider the grammar $S \to a S b ∣ ab$ . Which of the following statements are true?

(A)
$L (G) = {a^{n} b^{n} ∣ n \geq 1}$
(B)
$G$ is unambiguous
(C)
$G$ is in Chomsky normal form
(D)
The derivation of $aaabbb$ takes exactly 3 steps

Answer and solution

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

Each use of $S \to a S b$ adds one $a$ and one $b$ around $S$ , and $S \to ab$ ends it, so $L = {a^{n} b^{n} ∣ n \geq 1}$ . A is true.
Each string $a^{n} b^{n}$ has exactly one derivation (use $a S b$ $n - 1$ times then $ab$ ), so G is unambiguous. B is true.
$S \to a S b$ has three symbols on the right and $S \to ab$ has two terminals, so G is not in CNF. C is false.
$S \Rightarrow a S b \Rightarrow aa S bb \Rightarrow aaabbb$ is 3 steps. D is true.

PRACTICE 42 marks · NAT

For the grammar $S \to S S ∣ a$ , how many distinct leftmost derivations does the string $aaaa$ have?

Answer and solution

Answer: $5$

Leftmost derivations correspond one-to-one with parse trees.
Ignoring the leaves $a$ , every tree for $a^{n}$ is a full binary tree of $S$ -nodes with $n$ leaves, so the number of trees is the Catalan number $C_{n - 1}$ .
For $n = 4$ : $C_{3} = \frac{1}{4} (3 6) = 5$ .

PRACTICE 52 marks · MCQ

A PDA with one state $q$ accepts by empty stack. Its moves are $δ (q, a, Z_{0}) = {(q, AA Z_{0})}$ , $δ (q, a, A) = {(q, AAA)}$ , $δ (q, b, A) = {(q, ε)}$ and $δ (q, ε, Z_{0}) = {(q, ε)}$ , with no other moves. Which string is accepted?

(A)
$aabb$
(B)
$aabbbb$
(C)
$aaabbbb$
(D)
$abbb$

Answer and solution

Answer: (B)

Each $a$ adds two $A$ 's (on $Z_{0}$ it pushes $AA$ ; on $A$ it replaces one $A$ by $AAA$ ). Each $b$ pops one $A$ and needs an $A$ on top. The stack can be emptied only by popping $Z_{0}$ , which needs no $A$ above it, and after that no move is possible.
So $w$ is accepted exactly when the number of $b$ 's is twice the number of $a$ 's and no prefix has more $b$ 's than twice its $a$ 's (for example $aabbbb$ , and also $ababbb$ ).
A: $aabb$ leaves two $A$ 's on the stack, and the $ε$ -move cannot pop $Z_{0}$ under them. C: $aaabbbb$ leaves two $A$ 's. D: $abbb$ empties the $A$ 's after $abb$ and then has no move for $b$ on $Z_{0}$ .
B: $aabbbb$ gives $AAAA Z_{0}$ after $aa$ , the four $b$ 's pop the $A$ 's, and the $ε$ -move pops $Z_{0}$ . Answer B.

OFFICIAL GATE 2027 SYLLABUS WORDING

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

GATE CS

Context-free grammars and push-down automata

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