GATE CSE 2024 | Set 2 | Question: 42

Question

​​​​Consider a context-free grammar $\text{G}$ with the following $3$ rules.

\[
S \rightarrow a S,      S \rightarrow a S b S ,    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?

• A. $n_{a}(w)>n_{b}(w)$
• B. $n_{a}(w)>n_{c}(w)-2$
• C. $n_{c}(w)=n_{b}(w)+1$
• D. $n_{c}(w)=n_{b}(w) * 2$

Answer 1

The smallest string is “c”. So option A and D are invalid. Number of a’s = 0 and Number of c’s = 1. So as per option B 0>-1 which is true and same applies to other strings as well. Also number of b’s in smallest string are 0 so option C is true as well and same is the case for other strings.