Consider a context-free grammar $G$ with the following 3 rules: $$ S \to aS, \quad S \to aSbS, \quad S \to 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?

Question

cdquestions Admin · Accepted Answer

The grammar $G$ generates strings of the form: $$ w = a^p c b^q, $$ where the derivation of $c$ adds one $b$ and one $a$. Hence, the relationships between $n_a(w), n_b(w), n_c(w)$ can be analyzed: Option (A): Incorrect. While $n_a(w)$ is often greater than $n_b(w)$, there is no guarantee, as $n_a(w)$ and $n_b(w)$ depend on the specific derivation. Option (B): Correct. Since the derivation adds at least two $a$'s for every $c$, the inequality $n_a(w)>n_c(w) - 2$ holds. Option (C): Correct. Each derivation of $S \to aSbS$ adds one $b$ for every $c$, making $n_c(w) = n_b(w) + 1$. Option (D): Incorrect. The number of $c$'s is not necessarily twice the number of $b$'s. Final Answer: $$ \boxed{\text{(B), (C)}} $$

Answer

$n_a(w)>n_b(w)$

Answer

$n_a(w)>n_c(w) - 2$

Answer

$n_c(w) = n_b(w) + 1$

Answer

$n_c(w) = n_b(w) * 2$

Consider a context-free grammar \(G\) with the following 3 rules: \[ S \to aS, \quad S \to aSbS, \quad S \to 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?

Show Hint

The Correct Option is B

Solution and Explanation

Top Questions on Miscellaneous

Questions Asked in GATE CS exam