Consider a context-free grammar \(G\) with the following 3 rules.
\(S \rightarrow aS,\ S \rightarrow aSbS,\ S \rightarrow c\)
Let \(w \in L(G)\). Let \(n_a(w),\ n_b(w),\ n_c(w)\) denote the number of times \(a, b, c\) occur in \(w\), respectively. Which of the following statements is/are TRUE?
Answer
(B), (C)
Explanation
Follow the counts through a derivation, which starts with one \(S\). The rule \(S \rightarrow aSbS\) adds one \(a\), one \(b\) and one extra \(S\); \(S \rightarrow aS\) adds one \(a\); \(S \rightarrow c\) turns one \(S\) into \(c\). Every \(S\) must finally become a \(c\), so:
- \(n_c(w) = 1 + n_b(w)\), so (C) is true.
- Every \(b\) arrives with an \(a\), so \(n_a(w) \ge n_b(w) = n_c(w) - 1 \gt n_c(w) - 2\), and (B) is true.
The string \(w = c\) has \(n_a = n_b = 0\) and \(n_c = 1\). It breaks (A), since \(0 \gt 0\) is false, and (D), since \(1 \ne 0\).
Answer: B, C