ISRO CS 2023 Q.60: solution and answer

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

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Option (B): $aaaaabbb \in L (G)$ because it has $5 = 2 \cdot 2 + 1$ $a$ 's and $3 \geq 2$ $b$ 's, while $aaaabb \in / L (G)$ because it has an even number of $a$ 's.

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

From $T \to T b ∣ a$ : $T$ produces $a$ followed by any number of $b$ 's, so $T \Rightarrow^{*} a b^{k}$ for every $k \geq 0$ .
From $S \to aa S b ∣ T$ : each use of $S \to aa S b$ adds $aa$ on the left and one $b$ on the right. After $n$ such uses followed by $S \to T$ and $T \Rightarrow^{*} a b^{k}$ , the string is $(aa)^{n} a b^{k} b^{n} = a^{2 n + 1} b^{k + n}$ .
Hence $L (G) = {a^{2 n + 1} b^{m} : n \geq 0, m \geq n}$ . A string is in $L (G)$ exactly when all its $a$ 's come before all its $b$ 's, the number of $a$ 's is odd, say $2 n + 1$ , and the number of $b$ 's is at least $n$ .
Option (a): $aabbaabb$ has $b$ 's before $a$ 's, so it is not in $L (G)$ . The first part of the statement is false, so (a) is false.
Option (b): $aaaaabbb$ has $a^{5}$ , so $n = 2$ , and $m = 3 \geq 2$ . It is in $L (G)$ . $aaaabb$ has four $a$ 's, an even number, so it is not in $L (G)$ . Both parts hold, so (b) is true.
Option (c): $aaaabb$ has an even number of $a$ 's, so it is not in $L (G)$ . The first part is false, so (c) is false.
Option (d): $aaabb$ has $a^{3}$ , so $n = 1$ , and $m = 2 \geq 1$ . It is in $L (G)$ . But $aaaaabbb$ is also in $L (G)$ (shown in (b)), so the claim that it does not belong is false. (d) is false.

KEY IDEA

Unroll the grammar to get a closed form. The rule $S \to aa S b$ pairs two $a$ 's with one $b$ , and $T \to T b ∣ a$ gives one $a$ followed by any number of $b$ 's. So $L (G) = {a^{2 n + 1} b^{m} : m \geq n}$ , which has an odd number of $a$ 's, all $a$ 's first, and at least $n$ $b$ 's.

WATCH OUT FOR

Forgetting the single $a$ that $T$ contributes, which makes the number of $a$ 's odd, not even. Another slip is checking only that the $b$ 's are at least half the $a$ 's and ignoring order, which wrongly accepts strings like $aabbaabb$ .

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

Answer and solution

More ISRO CFG & PDA questions