GATE 2024 CS2 Q.52: solution and answer

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$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The true statements are (B) and (C).

Official answer: B, CSource: Official answer key, GATE 2024 CS2 (IISc Bengaluru)

Track how each production changes the counts. $S \to a S$ adds one $a$ and keeps the number of $S$ symbols the same. $S \to a S b S$ adds one $a$ and one $b$ and raises the number of $S$ symbols by 1. $S \to c$ adds one $c$ and lowers the number of $S$ symbols by 1.
A derivation starts with one $S$ and ends with none. Let $k$ be the number of uses of $S \to a S b S$ , $j$ the number of uses of $S \to a S$ , and $m$ the number of uses of $S \to c$ . The number of $S$ symbols changes by $+ k - m$ , so $1 + k - m = 0$ , which gives $m = k + 1$ .
Only $S \to a S b S$ produces a $b$ , so $n_{b} = k$ . Only $S \to c$ produces a $c$ , so $n_{c} = m = n_{b} + 1$ . Option (C) is TRUE.
Both $S \to a S$ and $S \to a S b S$ produce one $a$ each, so $n_{a} = k + j = n_{b} + j \geq n_{b}$ .
(A): take $w = c$ , which is in $L (G)$ . Then $n_{a} = 0$ and $n_{b} = 0$ , so $n_{a} > n_{b}$ fails. FALSE.
(B): from (C), $n_{c} - 2 = n_{b} - 1$ . Since $n_{a} \geq n_{b} > n_{b} - 1$ , we get $n_{a} > n_{c} - 2$ for every $w \in L (G)$ . TRUE.
(D): for $w = c$ , $n_{c} = 1$ but $n_{b} * 2 = 0$ . FALSE. Since $n_{c} = n_{b} + 1$ always holds, $n_{c} = 2 n_{b}$ could only happen when $n_{b} = 1$ , and it fails for $w = c$ anyway.
Hence the TRUE statements are (B) and (C).

KEY IDEA

Count the $S$ symbols during the derivation. Each $S \to a S b S$ adds one $S$ , each $S \to c$ removes one, and the derivation goes from one $S$ to none. So $n_{c} = n_{b} + 1$ , and since every $b$ is paired with an $a$ , $n_{a} \geq n_{b}$ .

WATCH OUT FOR

Judging (A) by cases that have at least one $b$ and forgetting that $w = c$ is in the language, where $n_{a} = n_{b} = 0$ . Another slip is to read $n_{a} \geq n_{b}$ as strict, or to treat (D) as true from the single case $n_{b} = 1$ .

From the GATE 2024 CS2 paper. Every question of this paper · Download the full paper · All 9 CFG & PDA questions, with notes

GATE 2024 CS2 Q.52: solution and answer

Answer and solution

More CFG & PDA questions