Question 34

Examine the production rules of the grammar:

Let $n_a(w)$ and $n_b(w)$ denote the number of occurrences of 'a' and 'b' in string $w$:

• $S \to SaS$ introduces one 'a' and zero 'b's: $\Delta(n_a - n_b) = +1$.
• $S \to aSb$ introduces one 'a' and one 'b': $\Delta(n_a - n_b) = 0$.
• $S \to bSa$ introduces one 'a' and one 'b': $\Delta(n_a - n_b) = 0$.
• $S \to SS$ preserves the sum of differences from each subderivation.
• $S \to \epsilon$ produces the empty string with $n_a = n_b = 0$.

Because every production rule either increases $n_a$ by 1 without increasing $n_b$, or increases both $n_a$ and $n_b$ by 1 equally, every string generated by $G$ must satisfy the invariant:

Check each candidate string:

• (A) abab: $n_a = 2, n_b = 2 \implies n_a \ge n_b$. Generated by $S \implies SS \implies aSb \, aSb \implies abab$.
• (B) aaab: $n_a = 3, n_b = 1 \implies n_a \ge n_b$. Generated by $S \implies SaS \implies \dots$
• (C) abbaa: $n_a = 3, n_b = 2 \implies n_a \ge n_b$.
• (D) babba: $n_a = 2, n_b = 3 \implies n_a < n_b$. This violates the invariant and can never be generated by $G$.