GATE CS 2026 Set 1 Q.52: Context-Free Grammars, Pushdown Automata and CFLs

Consider the following context-free grammar $G$ .

S \rightarrow abaABAbba

A \rightarrow aaBBAb \mid bBabaa

B \rightarrow aBb \mid 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?

There is a string $s \in L(G)$ such that $n_1(s) < n_2(s)$

For every string $s \in L(G)$ , $n_1(s) \ge n_2(s)$

There is a string $s \in L(G)$ such that $n_1(s) > 2n_2(s)$

For every string $s \in L(G)$ , $n_1(s) \le 2n_2(s)$

Official answer and solution

Official answer: B and D
From: Official GATE 2026 answer key

Solution

Count the number of terminal $a$ 's and $b$ 's introduced by each production rule in $G$ .

Let $(\Delta a, \Delta b)$ denote the number of terminal $a$ 's and $b$ 's directly introduced by each production rule:

$S \rightarrow abaABAbba$ : $(\Delta a, \Delta b) = (3, 3)$ , which satisfies $\Delta b \le \Delta a \le 2\Delta b$ .
$A \rightarrow aaBBAb$ : $(\Delta a, \Delta b) = (2, 1)$ , which satisfies $\Delta b \le \Delta a \le 2\Delta b$ .
$A \rightarrow bBabaa$ : $(\Delta a, \Delta b) = (3, 2)$ , which satisfies $\Delta b \le \Delta a \le 2\Delta b$ .
$B \rightarrow aBb$ and $B \rightarrow ab$ : $(\Delta a, \Delta b) = (1, 1)$ , which satisfies $\Delta b \le \Delta a \le 2\Delta b$ .

Since every production rule in $G$ introduces at least as many $a$ 's as $b$ 's ( $\Delta a \ge \Delta b$ ) and at most twice as many $a$ 's as $b$ 's ( $\Delta a \le 2\Delta b$ ), summing over all derivation steps of any string $s \in L(G)$ yields:

n_2(s) \le n_1(s) \le 2n_2(s)

Thus (B) and (D) are true, while (A) and (C) are false.

Final answer

Options (B), (D)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 52 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source