GATE CS 2017 Set 1 Q34 — Context-free Grammars and Push-down Automata

To determine which string cannot be generated by the grammar $G$, we can analyze the properties of the strings generated by its production rules:

1. Finding the Invariant of the Grammar

Let $N_a(w)$ and $N_b(w)$ denote the number of occurrences of the symbols $a$ and $b$ in a string $w$, respectively. Let's analyze how each production affects these counts:

• $S \rightarrow \epsilon$: $N_a = 0$ and $N_b = 0$. Here, $N_a \ge N_b$.
• $S \rightarrow aSb$: Adds exactly one $a$ and one $b$. If the inner $S$ satisfies $N_a \ge N_b$, then the resulting string also satisfies $N_a \ge N_b$.
• $S \rightarrow bSa$: Adds exactly one $b$ and one $a$. If the inner $S$ satisfies $N_a \ge N_b$, then the resulting string also satisfies $N_a \ge N_b$.
• $S \rightarrow SaS$: Adds one $a$ and no $b$. This strictly increases the count of $a$ relative to $b$, preserving $N_a \ge N_b$.
• $S \rightarrow SS$: Concatenates two strings. If both satisfy $N_a \ge N_b$, their concatenation also satisfies $N_a \ge N_b$.

By induction, every string $w$ generated by $G$ must satisfy the invariant:

2. Testing the Options

• Option A ($abab$): $N_a = 2$, $N_b = 2$. Since $2 \ge 2$, it satisfies the invariant.
  Derivation: $S \Rightarrow SS \Rightarrow aSb S \Rightarrow ab S \Rightarrow ab aSb \Rightarrow abab$
• Option B ($aaab$): $N_a = 3$, $N_b = 1$. Since $3 \ge 1$, it satisfies the invariant.
  Derivation: $S \Rightarrow SaS \Rightarrow a SaS \Rightarrow a aSb S \Rightarrow aaab$
• Option C ($abbaa$): $N_a = 3$, $N_b = 2$. Since $3 \ge 2$, it satisfies the invariant.
  Derivation: $S \Rightarrow SaS \Rightarrow aSb a S \Rightarrow abba S \Rightarrow abba SaS \Rightarrow abbaa$
• Option D ($babba$): $N_a = 2$, $N_b = 3$. Since $2 < 3$, this string violates the invariant $N_a(w) \ge N_b(w)$ and therefore cannot be generated by $G$.