ISRO CS 2025 Q.80: solution and answer

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}

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The grammar generates ${a^{m} b^{n} : 0 \leq m < n}$ , which is option (a).

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

Start with $T$ . The rules $T \to b T ∣ b$ give $T \Rightarrow^{*} b^{k}$ for every $k \geq 1$ , so $T$ always produces at least one $b$ and nothing else.
The rule $S \to a S b$ puts one $a$ on the left and one $b$ on the right of $S$ . Applying it $m \geq 0$ times gives $a^{m} S b^{m}$ .
Finish with $S \to T$ and then $T \Rightarrow^{*} b^{k}$ . This gives $a^{m} b^{k} b^{m} = a^{m} b^{m + k}$ with $m \geq 0$ and $k \geq 1$ . These are the only ways to derive a terminal string, since $S \to T$ is the only exit from $S$ .
Put $n = m + k$ . Then $n \geq m + 1$ , so $n > m$ . Conversely, any pair with $0 \leq m < n$ is generated by taking $k = n - m \geq 1$ . Hence $L (G) = {a^{m} b^{n} : 0 \leq m < n}$ .
Option (b) requires $m > 0$ , but $S \to T \Rightarrow b$ generates $b$ (with $m = 0$ ). Option (c) requires $n \leq m$ , but every generated string has $n > m$ . Option (d) requires $n = m$ , but $T$ forces at least one extra $b$ . So the answer is (a).

KEY IDEA

Each use of $S \to a S b$ adds one $a$ and one matching $b$ , while $T$ contributes at least one unmatched $b$ at the end, so the number of $b$ 's always exceeds the number of $a$ 's.

WATCH OUT FOR

Forgetting that $S \to T$ can be used immediately (with $m = 0$ ), and so wrongly requiring $m > 0$ , which gives option (b).

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.80: solution and answer

Answer and solution

More ISRO CFG & PDA questions