GATE 2026 CS (CS1) – Question 52
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?
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)$; (D) For every string $s \in L(G)$, $n_a(s) \le 2n_b(s)$
Explanation
Grammar: $S\to abaABAbba$, $A\to aaBBAb\mid bBabaa$, $B\to aBb\mid ab$.
**Counts of `a` minus `b`**
- $B$: every rule adds one `a` and one `b`, so $n_a(B)=n_b(B)=k\ge1$.
- $A\to bBabaa$: terminals `b,a,b,a,a` give 3 a's and 2 b's, plus $B$: $n_a-n_b=1$.
- $A\to aaBBAb$: terminals `a,a,b` give 2 a's, 1 b, plus $2B$ and a nested $A$: $n_a-n_b=1+\big(n_a(A)-n_b(A)\big)$.
So $n_a(A)-n_b(A)\ge1$ for every string from $A$.
- $S\to abaABAbba$: terminals `a,b,a,b,b,a` give 3 a's and 3 b's. With two $A$'s each contributing a surplus of at least 1 and $B$ contributing 0, $n_a(s)-n_b(s)\ge2$.
So $n_a(s)>n_b(s)$ for every $s\in L(G)$: (B) is true and (A) is false.
**Upper bound $n_a\le 2n_b$.**
- Base $A\to bBabaa$: $n_a=3+k\le 2(2+k)=4+2k$. True.
- Step $A\to aaBBAb$: $n_a=2+2k+a'$, $n_b=1+2k+b'$ with $a'\le2b'$ by induction, so $n_a\le2+2k+2b'\le2+4k+2b'=2n_b$. True.
- $S$: $n_a=3+a_1+a_2+k\le 3+2b_1+2b_2+k\le 2(3+b_1+b_2+k)=2n_b$. True.
So $n_a\le2n_b$ always: (D) is true and (C) is false.
Answer: B, D.