ISRO CS 2023 Q.57: solution and answer

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}

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}$ , option (a).

Official answer: ASource: ISRO's revised and final answer key of 16 February 2024

Start with $T$ . The rules $T \to b T ∣ b$ give $T \Rightarrow^{*} b^{k}$ for every $k \geq 1$ . The only way to stop is $T \to b$ , so at least one $b$ is always produced.
Now consider $S$ . Using $S \to a S b$ exactly $m$ times ( $m \geq 0$ ) puts one $a$ on the left and one $b$ on the right each time, giving $a^{m} S b^{m}$ .
Finish with $S \to T$ and $T \Rightarrow^{*} b^{k}$ with $k \geq 1$ . The string is $a^{m} b^{k} b^{m} = a^{m} b^{m + k}$ .
Put $n = m + k$ . Since $k \geq 1$ , we get $n \geq m + 1$ , that is $m < n$ , with $m \geq 0$ . The case $m = 0$ is $S \to T$ directly, giving $b^{n}$ with $n \geq 1$ . Conversely, every pair with $0 \leq m < n$ is obtained by taking $k = n - m \geq 1$ .
So $L (G) = {a^{m} b^{n} : 0 \leq m < n}$ , which is option (a).
Option (b) forces $m > 0$ , which wrongly excludes strings such as $b$ and $bb$ . Option (c) requires at least as many $b$ 's as... no: it requires $n \leq m$ , so no more $b$ 's than $a$ 's, but every string of $G$ has strictly more $b$ 's than $a$ 's. Option (d) needs equal numbers, but the last step $T \to b$ always leaves at least one extra $b$ .

KEY IDEA

Split the grammar into its two parts. $T$ generates $b^{k}$ with $k \geq 1$ , and $S \to a S b$ wraps it with $m$ matching pairs of $a$ and $b$ . So the number of $b$ 's exceeds the number of $a$ 's by exactly $k \geq 1$ .

WATCH OUT FOR

Choosing (d) because the rule $S \to a S b$ looks like $a^{n} b^{n}$ , or choosing (b) by forgetting that $S \to T$ directly gives strings with no $a$ at all.

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

ISRO CS 2023 Q.57: solution and answer

Answer and solution

More ISRO CFG & PDA questions