The GATE Grind

GATE 2024 CS (CS2) – Question 52

Theory of Computation · Context-Free Grammars and Pushdown Automata · 2 marks · Multiple select

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?

  1. $n_a(w)>n_b(w)$
  2. $n_a(w)>n_c(w)-2$
  3. $n_c(w)=n_b(w)+1$
  4. $n_c(w)=n_b(w)*2$

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$.

Answer: B, C.

More Context-Free Grammars and Pushdown Automata questions

All Context-Free Grammars and Pushdown Automata questions →