\documentstyle[11pt,twoside]{article}
\input{../macros-course}

\addtolength{\topmargin}{-.8in}
\setlength{\textheight}{9in}
\pagestyle{empty}
\setlength{\parskip}{\medskipamount}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\noindent
\hfil  {\large $S \rightarrow a S b \mid SS \mid \epsilon$ }\\  \hfil

\thm
This grammar produces exactly 
%	the following set of string over $a, b$:\\
%	$\{ w \mid w \mbox{ has an equal number of $a$'s and $b$'s, 
%	and each prefix of $w$ has at least as many $a$'s as $b$'s} \}$.
the set of $a,b$-strings that
(1) have an equal number of $a$'s and $b$'s and 
(2) have at least as many $a$'s as $b$'s in each prefix. 
\ethm
\pf
\hfil
{\bf I.} All strings of length $n$ produced by the grammar have this form.\\
\hfil

By induction on $n$.
For the base case, take $n=2$: the only string of length 2 produced by
the grammar is $ab$, which has the desired form.

For the inductive case, consider any string $w$ of length $k$ produced by 
the grammar,  and consider
the last step of the derivation in which an $S$ was replaced by $aSb$:
\[
S \rightarrow \cdots \rightarrow R S T \rightarrow R aSb T \rightarrow 
	\cdots \rightarrow w
\]
for some strings $R$ and $T$ made of $a$'s, $b$'s and $S$'s.
Since the $S$ in $RaSbT$ does not get expanded to $aSb$ again,
it eventually disappears (possibly spawning more $S$'s first), 
so $S\rightarrow \cdots RabT\rightarrow \cdots \rightarrow uabv=w$ 
for some strings $u$ and~$v$.
The string $uv$ is therefore also produced by the grammar, by the derivation
$S\rightarrow \cdots \rightarrow R S T \rightarrow RT \rightarrow \cdots 
\rightarrow uv.$
Since the length of $uv$ is less than $k$, 
by our inductive hypothesis it has the desired form.
Since $uv$ has the same number of $a$'s and $b$'s, so does $w$.
Also, since $uv$ has at least as many $a$'s as $b$'s in any prefix, 
so does $w$.\\

\hfil
{\bf II.}  The grammar produces all strings of length $n$ having this form.\\
\hfil

By induction on $n$.
For the base case, take $n=2$:  there is only one string, $ab$, satisfying
the prefix property, and it is produced by the grammar.

For the inductive step, consider any string $w$ of length $k$ having this form.
Let $u$ be the shortest prefix of $w$ that contains an equal number of
$a$'s and $b$'s, so $w=uv$.  

If $v$ is not empty, then $u$ and $v$ are
both strings having this form:  clearly, $v$ has the same number of $a$'s as
$b$'s because $u$ does; 
since the prefix property holds for $w$, it holds for $u$ and 
it holds for $v$ (because $u$ has an equal number of $a$'s and $b$'s).
Since $v$ is not empty, both $u$ and $v$ have length less than $k$, and 
by our inductive hypothesis, we can derive each of them.
To derive $w$ therefore, put $S\rightarrow SS$ as the first step, 
use the derivation for $u$ for the first $S$ and 
the derivation for $v$ for the second $S$.

If $v$ is empty, then $w=xsy$ for some letters $x$ and~$y$ 
and some nonempty string~$s$.
The letter $y$ must be an $a$ for $w$ to satisfy the prefix property.
The letter $x$ must be a $b$ because otherwise, the prefix $as$ 
has more $b$'s than $a$'s. So $w=asb$ for some nonempty string $s$.
\begin{quote}
\begin{claim}
The string $s$ has the desired form.
\end{claim}
\pf
Clearly it has an equal number of $a$'s and $b$'s.
We will show by contradiction that it has the prefix property.
Suppose there were a prefix $s_1$ of $s$ (so $s= s_1 s_2$)
that had more $b$'s than $a$'s.
Then there must be a prefix of $as_1$ that has an equal number of 
$a$'s and $b$'s.  But this is a contradiction:  there cannot be 
such a prefix because $v$ is empty, which by our choice of $u$ means
there is no proper prefix of $w$ with an equal number of $a$'s and $b$'s.
\epf
\end{quote}

Since $s$ has length less than $k$, we know by our inductive hypothesis
that we can derive~$s$.
Thus, to derive $w$, put $S\rightarrow aSb$ as the first step, 
and then expand $S$ using use the derivation for~$s$.
\end{proof}

\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
{\large $S \rightarrow aB \mid bA \mid \epsilon $}\\ \smallskip
{\large $A \rightarrow aS \mid bAA$}\\ \smallskip
{\large $B \rightarrow bS \mid aBB$}
\end{center}

\thm This grammar produces exactly the set of $a,b$-strings that have
an equal number of $a$'s and $b$'s.  
\ethm
\pf
We would like to prove this by (strong) induction on $n$. 
We need to show that all strings generated by the grammar have an
equal number of $a$'s and $b$'s, and any string with an equal number
of $a$'s and $b$'s is generated by the grammar.
We will prove these two parts separately.
To make the proof go through (in each of these parts) we need to
strengthen the statement to be proved by also considering derivations
that begin with $A$ or~$B$.  

\begin{quote}
{\bf I.} 
For all even $n$, any string of length $n$ produced by the grammar
has an equal number of $a$'s and $b$'s; moreover, $A$ and $B$ generate
no strings of length~$n$.
%  any derivation beginning with $A$ or $B$ produces no strings of length $n$.
For all odd $n$, this grammar produces no strings of length $n$, 
and any string of length $n$ produced by $A$   % derivation beginning with $A$ 
has one more $a$ than $b$'s and any string of length $n$ produced by $B$
%	starting with $B$ 
has one more $b$ than $a$'s.
\end{quote}

Base case:  $n=0$.
This grammar produces one string of length 0, the empty string;
any expansion of $A$ and $B$ produces one letter ($a$ or $b$), so 
$A$ and $B$ produce no strings of length~0.

Inductive step:  Assume the statement {\bf I} is true for $n=0,\ldots, k$.
If $k+1$ is odd then it is clear that $S$ cannot generate any strings
of length $k+1$ since $S\rightarrow aB$ or $S\rightarrow bA$, but
by the inductive hypothesis
neither $A$ nor $B$ generates (even) strings of length~$k$.
Now consider any string of length $k+1$ generated by $A$. 
If the first step of the derivation is $A\rightarrow aS$,
then $S$ expands into a string of length $k$ (even), which by the inductive
hypothesis, has an equal number of $a$'s and $b$'s.
If instead the first step of the derivation is $A\rightarrow bAA$,
then each of the $A$'s in $bAA$ expands into a string of length at
most $k$, which by the inductive hypothesis has one more $a$ than $b$'s. 
Hence, all strings of length $k+1$ generated by $A$
have one more $a$ than $b$'s.  
The situation is similar for $B$.  
This proves the case of $k+1$ odd.

Suppose $k+1$ is even.
Consider any string $w$ of length $k+1$ produced by the grammar. 
Suppose the first step in the derivation is $S\rightarrow aB$.
Then the derivation must expand $B$ into a string of length $k$, which
by the inductive hypothesis, has one more $b$ than $a$.  Therefore, 
$w$ has an equal number of $a$'s and $b$'s.
The situation is similar if the first step of the derivation 
is $S\rightarrow bA$. 

We now show by contradiction that $A$ cannot produce a string of length $k+1$.
For contradiction, let $w$ be a string of length $k+1$ produced by~$A$.
Suppose the first step in its derivation is $A\rightarrow aS$.
Then the derivation must expand $S$ into a string of even length $k$, 
but we know by the inductive hypothesis that this is impossible.
Suppose instead that the first step in its derivation is $A\rightarrow bAA$.
Then the derivation must expand the $AA$ into a string of odd length.
But each $A$ is expanded into a string of length $k$ or less, and 
by the inductive hypothesis, this string must have odd length.
Since the sum of two odd numbers is even, we have a contradiction.
Therefore we conclude that 
%	Then since each of the $A$'s in $bAA$ expands into a string of odd
%	length less than $k+1$ it is clear that 
$A$ cannot generate a string of length $k+1$. 
The situation is similar for $B$. 
Thus we have proven the case of $k+1$ even.

\newpage
\begin{quote}
{\bf II.} 
For all even $n$, this grammar produces all strings of length $n$ with
an equal number of $a$'s and $b$'s.
For all odd $n$, $A$ generates all
strings of length $n$ with one more $a$ than $b$'s and $B$ generates
all strings of length $n$ with one more $b$ than $a$'s.
\end{quote}

Base case: $n=0$.  There is only one string of length 0, the empty
string, which is produced by this grammar.

Assuming the statement is true for $n \leq k$ ($k \geq 0$) we now
prove it for $k+1$.

Suppose $k+1$ is even.
Let $w$ be any string of length $k+1$ with an equal number of $a$'s and~$b$'s.
If $w$ starts with $a$, then let the first step of the derivation be
$S\rightarrow aB$.
By the inductive hypothesis, $B$ generates all strings of (odd) length $k$ 
with one more $b$ than $a$'s, in particular, the desired suffix of~$w$.
This shows that the grammar produces $w$, and 
proves the case of $k+1$ even.


Suppose $k+1$ is odd.
Let $w$ be any string of length $k+1$ with one more $a$ than $b$'s. 
We show how this is generated by $A$. 
If the string starts with an $a$ then put $A\rightarrow aS$ and use the
inductive hypothesis for $S$ to generate the whole string. 
If the string starts with $b$ then find a prefix $bp$ (for some string $p$)
of $w$ that has an equal number of $a$'s and $b$'s 
(which must exist since $w$ has more $a$'s than $b$'s).
Then $w=bpq$ where $p$ and $q$ are each strings of length at most $k$
having one more $a$ than $b$. 
By the inductive hypothesis, each of $p$ and $q$ is generated by $A$.
Thus, to derive $w$, put $S\rightarrow bAA$ as the first step and 
then derive $p$ from the first $A$ and $q$ from the second~$A$.
The situation is similar for strings of length $k+1$ that have one more $b$ 
than $a$'s. 
Thus we have proven the case of  $k+1$ odd.

\end{proof}

\end{document}
