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: (B) $n_a(w)>n_c(w)-2$; (C) $n_c(w)=n_b(w)+1$
Explanation
Grammar: $S\to aS\mid aSbS\mid c$.
- Every use of $S\to aSbS$ adds one `b` and one extra $S$ (one more place that must end in `c`). $S\to aS$ keeps the number of $S$'s. Starting from one $S$, we end with $1+(\#\text{ of }aSbS\text{ uses})$ copies of `c`, and `b` appears once per use. So $n_c=n_b+1$ is true: **(C)**.
- (D) $n_c=2n_b$ is false (e.g. `c` has $n_c=1,n_b=0$).
- Each `b` comes from an $aSbS$ rule that also adds an `a`, so $n_a\ge n_b$. Equality is possible: `acbc` has $n_a=n_b=1$. So $n_a>n_b$ is **not** always true: (A) is false.
- Since $n_c-2=n_b-1$ and $n_a\ge n_b>n_b-1$, we always have $n_a>n_c-2$: **(B)** is true.
Answer: B, C.