GATE 2026 CS1 Q.52: solution and answer

GATE 2026 · CS1Q.52 · 2 marks · MSQ

Consider the following context-free grammar $G$ .

S A B \to aba A B A bba \to aa B B A b ∣ b B abaa \to a B b ∣ ab

In the above grammar, $S$ is the start symbol, $a$ and $b$ are terminal symbols, and $A$ and $B$ are non-terminal symbols.

Let $L (G)$ be the language generated by the grammar $G$ . For a string $s \in L (G)$ , let $n_{1} (s)$ be the number of $a$ 's in $s$ and $n_{2} (s)$ be the number of $b$ 's in $s$ .

Which of the following statements is/are true?

(A)
There is a string $s \in L (G)$ such that $n_{1} (s) < n_{2} (s)$
(B)
For every string $s \in L (G)$ , $n_{1} (s) \geq n_{2} (s)$
(C)
There is a string $s \in L (G)$ such that $n_{1} (s) > 2 n_{2} (s)$
(D)
For every string $s \in L (G)$ , $n_{1} (s) \leq 2 n_{2} (s)$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

(B) and (D) are true. (A) and (C) are false.

Official answer: B, DSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

Let $d (w) = n_{1} (w) - n_{2} (w)$ for a derived string $w$ . The grammar is context-free and $d$ is additive over concatenation, so we can compute $d$ for each non-terminal separately.
$B \to a B b ∣ ab$ generates exactly $a^{k} b^{k}$ with $k \geq 1$ . So $d (B) = 0$ and $B$ always contributes at least one $b$ .
$A \to b B abaa$ : the terminals $b, a, b, a, a$ contribute 3 a's and 2 b's, so $d = 1$ plus $d (B) = 0$ . This gives $d (A) = 1$ and at least $2 + 1 = 3$ b's.
$A \to aa B B A b$ : the terminals $a, a, b$ contribute $d = 2 - 1 = 1$ . The two $B$ 's contribute $0$ and add at least 2 b's. Using this rule $m$ times and then $A \to b B abaa$ gives $d (A) = 1 + m$ and $n_{2} (A) \geq 3 + 3 m$ .
$S \to aba A B A bba$ contains TWO copies of $A$ . The terminals $aba$ give $d = 1$ and $bba$ give $d = - 1$ , and $d (B) = 0$ . So with $m_{1}, m_{2} \geq 0$ uses of the recursive rule in the two copies, $d (s) = 1 + (1 + m_{1}) + 0 + (1 + m_{2}) - 1 = 2 + m_{1} + m_{2} \geq 2$ .
Hence $n_{1} (s) - n_{2} (s) \geq 2 > 0$ for every $s \in L (G)$ . So $n_{1} > n_{2}$ always: (A) is false and (B) is true.
Count the b's. The b's come from $aba$ (1), $bba$ (2), the middle $B$ (at least 1), and the two $A$ 's (at least $3 + 3 m_{1}$ and $3 + 3 m_{2}$ ). So $n_{2} (s) \geq 10 + 3 (m_{1} + m_{2})$ .
Put $M = m_{1} + m_{2}$ . Then $d (s) = 2 + M$ and $n_{2} (s) \geq 10 + 3 M$ , so $d (s) \leq n_{2} (s)$ for every $s$ . Therefore $n_{1} = n_{2} + d \leq 2 n_{2}$ for every string: (D) is true and (C) is false.
Check on the smallest string: $B \to ab$ everywhere and $A \to b B abaa$ in both copies. Then $n_{1} = 12$ and $n_{2} = 10$ , so $n_{1} > n_{2}$ and $n_{1} \leq 2 n_{2} = 20$ . This agrees with the above.

KEY IDEA

Track the difference $n_{1} - n_{2}$ for each non-terminal. $B$ gives $0$ , each $A$ gives $1 + m$ , and $S$ has two copies of $A$ , so the difference is at least 2. The b-count grows at least three times as fast as the difference, which gives $n_{1} \leq 2 n_{2}$ .

WATCH OUT FOR

Treating $S \to aba A B A bba$ as if it had only one $A$ . It has two. Dropping one $A$ gives the wrong string counts, such as $n_{2} = 7$ and $n_{1} = 8$ for the smallest string. The correct smallest string has $n_{2} = 10$ and $n_{1} = 12$ . The conclusions (B) and (D) still hold.

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

GATE 2026 CS1 Q.52: solution and answer

Answer and solution

More CFG & PDA questions