Context free grammar for strings with more $a$'s than $b$'s

Question

I would like to prove that the grammar $G$ with the rules $$ S \to SS \mid aSb \mid bSa \mid a \mid \varepsilon $$ generates the language $L = \{w \mid \text{$w$ has at least as many $a$'s as $b$'s}\}$.

Question

My proof is below, but it feels rather clunky and unintuitive. Does anyone have an alternative proof and/or suggestions for how I can improve what I have?

Proof

Step 1. First, we will show that $\mathcal{L}(G) \subseteq L$. This is immediate from the fact that no rule generates more $b$'s than $a$'s. Let $w \in \mathcal{L}(G)$, generated by $G$ via $S = u_1 \Rightarrow \dots \Rightarrow u_n = w$. In each step where a $b$ is added, an $a$ must also be added. Because $w_1$ has an equal number of $a$'s and $b$'s, each subsequent $w_i$ must have at least many $a$'s than $b$'s. Therefore, $w_n \in L$, and so $\mathcal{L}(G) \subseteq L$.

Step 2. Next, we will show that $G$ generates all strings with an equal number of $a$'s and $b$'s. Let $K$ be the set of all such strings. We argue by induction to show that $K \subseteq \mathcal{L}(G)$.

Base step. Let $w \in K$ such that $|w| = 0$. Then $w$ can be generated by $G$ via $S \Rightarrow \varepsilon$.

Inductive step. Suppose $G$ can generate any string in $K$ length less than or equal to $n$. Let $w \in K$ such that $|w| = n + 1$. We distinguish several cases:

1. $w = aub$ for some string $u$. Because $w$ has an equal number of $a$'s and $b$'s, $u$ must also have an equal number of $a$'s and $b$'s. This implies $u \in K$, and by the inductive hypothesis, $S \Rightarrow^* u$. Thus, $w$ is generated by $G$ via $S \Rightarrow aSb \Rightarrow^* aub$.

2. $w = bua$ for some string $u$. This is the same as the previous case.

3. $w$ starts and ends with $a$. But because $w$ has the same number of $a$'s and $b$'s, there must be a point where the number of $b$'s “catches up” with the number of $a$'s. This implies $w = uv$, where $u, v \in K$ are non-empty. By the inductive hypothesis, $S \Rightarrow^* u$ and $S \Rightarrow^* v$. Thus, $w$ is generated by $G$ via $S \Rightarrow SS \Rightarrow^* uS \Rightarrow^* uv$.

By induction, we conclude that $K \subseteq \mathcal{L}(G)$.

Step 3. Finally, we will show that $L \subseteq \mathcal{L}(G)$. Let $w \in L$. Consider the first occurrence of $b$ in $w$. I claim that this occurrence of $b$ must be contained in some substring of $w$ that has an equal number of $a$'s and $b$'s. To see this, we consider several cases:

1. $w$ starts with $a$. Then there is an $a$ to the left of $w$, so $ab$ is a substring of $w$ that contains the first occurrence of $b$.

2. $w$ starts with $b$. Because $w$ has at least as many $a$'s as $b$'s, there must be some prefix of $w$ that has an equal number of $a$'s and $b$'s.

Identify the largest possible substring and call it $v_1$. Note that $v_1 \in K$. Then $w = u_1v_1x$, where $u_1$ consists solely of $a$'s. Note that $x$ must have at least as many $a$'s as $b$'s. If not, then one can write $u_1 = y_1y_2$ and construct a substring $y_2v_1x \in K$. But because $v_1$ was the largest possible substring, this is a contradiction.

Repeat this procedure for the first occurrence of $b$ within $x$ to get $x = u_2v_2y$. Then repeat this procedure for the first occurrence of $b$ within $y$. Doing this until no more $b$'s remain, we can write $w$ as $u_1v_1u_2v_2\dots u_nv_nu_{n+1}$, where each $u_i$ contains only $a$'s and each $x_i \in K$. Because $K \subseteq \mathcal{L}(G)$ and $G$ can clearly generate any string consisting solely of $a$'s, $w$ can be generated by $G$ via

$$ S \Rightarrow^* \underbrace{S\dots S}_{2n + 1} \Rightarrow^* u_1v_1u_2v_2\dots u_nv_nu_{n+1} = w. $$

So $w \in \mathcal{L}(G)$, completing the proof.

Answer 1

Here is a somewhat simpler proof for $L \subseteq \mathcal{L}(G)$.

Apply induction directly to the claim that any string in $L$ can be generated by $G$.

As before, the base case is done by $S \rightarrow \varepsilon$.

For a nonempty string, counting $a$ as +1 and $b$ as -1, consider the partial sums:

If any intermediate (i.e., not first or last) partial sum is 0, break the string at that point, and apply $S \rightarrow SS$, and apply the induction hypothesis to both parts.

If no intermediate partial sum is 0 and the last partial sum (which is the full sum) is 0, then the first and last symbols must be different. Apply $S \rightarrow aSb$ or $S \rightarrow bSa$ as appropriate, and apply the induction hypothesis to the middle (the string with the first and last symbols removed).

If no intermediate partial sum is 0 and the last partial sum (which is the full sum) is positive (it cannot be negative), then the first symbol must be $a$. Apply $S \rightarrow SS$ and then apply $S \rightarrow a$ to the first of the two $S$; apply the induction hypothesis to the string with the starting $a$ removed.