3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

Graph showing the values 0, 1, 0, -1, -2, -1, 0, corresponding to the string a, b, b, b, a, a.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.