GATE 2024 CS (CS2) – Question 52
Consider a context-free grammar $G$ with rules $S\to aS$, $S\to aSbS$, $S\to c$. Let $w\in L(G)$ and let $n_a(w), n_b(w), n_c(w)$ denote the number of times $a,b,c$ occur in $w$. Which of the following statements is/are TRUE?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (A) $n_a(w)>n_b(w)$; (B) $n_a(w)>n_c(w)-2$; (C) $n_c(w)=n_b(w)+1$
Explanation
Each application of S→aSbS adds one a, one b and one extra S, so n_c = n_b + 1 (C). Every b comes with at least one a (S→aSbS), and S→aS adds only a's, so n_a ≥ n_b, with at least one more a whenever c exists... giving n_a > n_b (A) and n_a ≥ n_b, so n_a > n_c − 2 = n_b − 1 (B).