We first show that each string generated by this grammar has the same number of a’s and b’s. Proceed by induction over the length $N$ of the derivation.
- Case base: $N = 1$ The only string derivable with a derivation of length $N = 1$ is $ e(S → e):$ it trivially holds that the number of $a’s$ and $b’s$ in $e$ is the same.
- Inductive step: Assume that all the strings $w$ derivable from $S$ with a derivation of length at most $N$ have an equal number of $a’s$ and $b’s$. Consider now a string $w′$ derivable from $S$ with a derivation of length $N + 1$. Clearly, the first production used in the derivation that yields $w′$ is either $S → aSbS$ or $S → bSaS$. In either cases, the remaining $N$ productions can be ideally split into two derivations: one that generates a string $w1$ from the first $S$ and another that generates a string $w2$ from the second $S$. By induction, it clearly holds that in both $w1$ and $w2$ the number of $a’s$ is equal to the number of $b’s$. Moreover, since $w$ is either $aw_{1}bw_{2}$ or $bw_{1}aw_{2}$, we get that the number of $a’s$ in $w$ is equal to the number of $b’s$.
To complete the proof, we still need to show that any string $w$ with an equal number of $a’s$ and $b’s$ can be derived from $S$.
Proceed by induction on the length of $w$. •
- Case base: $|w| = 0$, i.e. $w = e$. It is clear that $w$ can be derived from $S (S → e)$.
- Inductive step: Assume that all the strings $w$ with an equal number of $a’s$ and $b’s$ and of length up to $2N$ are derivable from $S$. Consider now a string $w′$ with an equal number of $a’s$ and $b’s$ of length $2(N + 1)$. W.l.o.g. assume that the first symbol in $w′$ is an $a$. Let $2\leq j \leq2N+2$ be the first index such that the substring of $w′$ from position $1$ to position $j$ has an equal number of $a’s$ and $b’s$. Notice that such $j$ always exists, since in the worst case $j = 2N + 2$ will do it.
- If $j = 2N + 2$, then this means that $w′$ is of the form $a^{N}b^{N}$ and thus can be derived from $S$ by the derivation $S ⇒ aSbS ⇒ aSb ⇒ aaSbSb ⇒ aaSbb ⇒ . . . ⇒ a^{N}b^{N}$.
- Otherwise $(i.e. j < 2N + 2)$, notice that, since the symbol at position $j$ must be a $b$, $w′$ can be written as $w′ = aw_{1}bw_{2}$, where $w_{1}$ and $w_{2}$ are both strings of length at most N, each having an equal number of $a’s$ and $b’s$. Thus, by induction, both $w_{1}$ and $w_{2}$ can be derived from $S$ from which it follows that $w′$ can also be derived from $S$.
Ref: https://cs.nyu.edu/courses/fall03/V22.0453-001/ans3.pdf
