The GATE Grind

GATE 2026 CS (CS1) – Question 52

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple select

Consider the following context-free grammar $G$:
$$S \to abaABAbba$$
$$A \to aaB BAb \mid bB a b a a$$
$$B \to 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_a(s)$ be the number of $a$'s in $s$ and $n_b(s)$ be the number of $b$'s in $s$. Which of the following statements is/are true?

  1. There is a string $s \in L(G)$ such that $n_a(s) < n_b(s)$
  2. For every string $s \in L(G)$, $n_a(s) \ge n_b(s)$
  3. There is a string $s \in L(G)$ such that $n_a(s) > 2n_b(s)$
  4. For every string $s \in L(G)$, $n_a(s) \le 2n_b(s)$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) For every string $s \in L(G)$, $n_a(s) \ge n_b(s)$; (C) There is a string $s \in L(G)$ such that $n_a(s) > 2n_b(s)$

Explanation

Count occurrences of $a$ and $b$ generated by each non-terminal:
1. Non-terminal $B$:
$B \to aBb \mid ab$. Every step adds equal numbers of $a$'s and $b$'s. Hence for any string derived from $B$, $n_a(B) = n_b(B) = k$ for some $k \ge 1$.
2. Non-terminal $A$:
- Production 1: $A \to aaBBAb$. Number of $a$'s added = $2 + n_a(B) + n_a(B) + n_a(A) = 2 + 2k_1 + n_a(A)$. Number of $b$'s added = $1 + 2k_1 + n_b(A)$. Here, $a$'s exceed $b$'s by at least 1.
- Production 2: $A \to bB a b a a$. Number of $a$'s = $1 + n_a(B) + 2 = 3 + k$. Number of $b$'s = $1 + n_b(B) + 1 = 2 + k$. Here, $n_a = k + 3 > k + 2 = n_b$.
In all derivations from $A$, $n_a(A) > n_b(A)$.
3. Start symbol $S \to abaABAbba$:
Explicit terminals in $S$: 5 $a$'s and 4 $b$'s ($n_a = 5, n_b = 4$).
Since $n_a(B) = n_b(B)$ and $n_a(A) > n_b(A)$, the total count across any complete sentential form satisfies $n_a(s) > n_b(s)$. Thus for every string $s \in L(G)$, $n_a(s) \ge n_b(s)$ is strictly TRUE. (Statement B is true; Statement A is false).
4. Furthermore, by repeatedly expanding $A \to aaBBAb$ and choosing large expansions, the ratio $n_a(s) / n_b(s)$ can be made strictly greater than 2 for certain strings. Hence Statement (C) is true, and Statement (D) is false.

Therefore, statements (B) and (C) are true.