ISRO CS 2025 Q.33: solution and answer

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The string $aa c bb$ , option (b), is generated by the grammar.

Official answer: BSource: ISRO's final answer key of 15 May 2026

Expand $A$ : each use of $A \to a A b$ adds one $a$ on the left and one $b$ on the right, and $A \to c$ ends the derivation. So $L (A) = {a^{n} c b^{n} : n \geq 0}$ .
Expand $B$ : each use of $B \to b B d$ adds one $b$ on the left and one $d$ on the right, and $B \to e$ ends it. So $L (B) = {b^{n} e d^{n} : n \geq 0}$ .
Since $S \to A ∣ B$ , a string is generated only if it has the form $a^{n} c b^{n}$ or $b^{n} e d^{n}$ .
(a) $a cc bb$ has two $c$ 's. Every string of $G$ has exactly one $c$ or exactly one $e$ , so it is not generated.
(b) $aa c bb = a^{2} c b^{2}$ is of the form $a^{n} c b^{n}$ with $n = 2$ . Derivation: $S \Rightarrow A \Rightarrow a A b \Rightarrow aa A bb \Rightarrow aa c bb$ . It is generated.
(c) $aba e d$ has no $c$ , so it is not of the form $a^{n} c b^{n}$ . It is not of the form $b^{n} e d^{n}$ either, because it starts with $a$ . It is not generated.
(d) $aa e bb$ mixes $a$ 's with $e$ . $A$ never produces $e$ and $B$ never produces $a$ , so it is not generated.
Only option (b) is derivable from $G$ .

KEY IDEA

Work out the language of each non-terminal separately. $A$ gives $a^{n} c b^{n}$ and $B$ gives $b^{n} e d^{n}$ . Then check each string against the two forms.

WATCH OUT FOR

Treating the symbols as freely mixable, for example accepting $a cc bb$ or $aa e bb$ . In this grammar $a$ 's pair only with $c$ and $b$ 's, and $e$ only comes with $b$ 's and $d$ 's. Each string also has exactly one $c$ or one $e$ .

From the ISRO CS 2025 paper. Every question of this paper · The full paper (PDF, ISRO) · All 6 ISRO CFG & PDA questions, with notes

ISRO CS 2025 Q.33: solution and answer

Answer and solution

More ISRO CFG & PDA questions