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

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

\begin{document}


\noindent
\hfil {\large $S \rightarrow aB \mid bA \mid \epsilon $}\\ \hfil
\noindent
\hfil {\large $A \rightarrow aS \mid bAA$}\\ \hfil
\noindent
\hfil {\large $B \rightarrow bS \mid aBB$}\\ \hfil

\thm This grammar produces exactly the set of $a,b$-strings that have
an equal number of $a$'s and $b$'s.  
\ethm
\pf
\hfil
{\bf I.} All strings of length $n$ produced by the grammar have this form.\\
\hfil

The proof is by induction on $n$. To make the proof go through we
strengthen the inductive hypothesis. The new inductive hypothesis is:

If $n$ is even then only $S$ generates strings of length $n$. If $n$
is odd then only $A$ and $B$ generate strings of length $n$. Further,
if $n$ is even, then all strings of length $n$ generated by $S$ have
an equal number of $a$'s and $b$'s. If $n$ is odd, then all strings of
length $n$ generated by $A$ have one more $a$ than $b$'s and all
strings of length $n$ generated by $B$ have one more $b$ than $a$'s.

Base case. The inductive hypothesis is easily seen to be true for $n =
0$ and $n = 1$. 

Assuming the inductive hypothesis for $n \leq k, (k \geq 1)$ we now
prove it for $k+1$.

If $k+1$ is odd then it is clear that $S$ cannot generate any strings
of length $k+1$ since $S$ can only expand into $aB$ or $bA$, but
neither $A$ nor $B$ generates strings of length $k$ by the inductive
hypothesis. Now consider $A$. If it expands into $aS$ then since all
strings of length $k$ generated by $S$ have an equal number of $a$'s
and $b$'s it is clear that it generates strings of length $k+1$ with
one more $a$ than $b$'s. If it expands into $bAA$ then each of the
$A$'s in $bAA$ expands into an even string of length at most $k$ with
one more $a$ than $b$'s. Hence, by the inductive hypothesis the
strings of length $k+1$ generated by $bAA$ has one more $a$ than
$b$'s. The situation is similar for $B$. This proves the hypothesis
for (odd) $k+1$.

If $k+1$ is even then we see that $A$ cannot generate any strings of
length $k+1$. If $A$ expands into $aS$ then since $S$ does not
generate any strings of length $k$, by the inductive hypothesis, it
cannot generate a string of length $k+1$. If $A$ expands into $bAA$
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$ itself cannot generate a
string of length $k+1$. The situation is similar for $B$. Now consider
$S$. If it expands into $aB$ then since $B$ generates strings of
length $k$ with one more $b$ than $a$, $S$ generates strings of length
$k+1$ with an equal number of $a$'s and $b$'s. The situation is
similar if $S$ expands into $bA$. Thus we have proven the hypothesis
for (even) $k+1$.

\hfil {\bf II.} The grammar produces all strings of length $n$ with an
equal number of $a$'s and $b$'s.\\ 
\hfil

As before we strengthen the inductive hypothesis to make the proof go
through. The new inductive hypothesis is 

If $n$ is even then $S$ generates all strings of length $n$ with an
equal number of $a$'s and $b$'s. If $n$ is odd, then $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.

Base case. The inductive hypothesis is easily seen to be true for
$n=0$ and $n=1$.

Assuming the inductive hypothesis for $n \leq k, (k \geq 1)$ we now
prove it for $k+1$.

If $k+1$ is even then consider any string of length $k+1$ with an
equal number of $a$'s and $b$'s. If the string starts with $a$ then
first expand $S$ into $aB$ and then since by the inductive hypothesis
$B$ generates all strings of length $k+1$ with one more $b$ than $a$'s
we get that $S$ generates the required string of length $k+1$. Hence
we have proven the inductive hypothesis for (even) $k+1$.

If $k+1$ is odd then consider 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 expand $A$ into $aS$ and use the inductive
hypothesis for $S$ to generate the whole string. If the string starts
with a $b$ then look at the counter: (number of $a$'s - number of
$b$'s) for all prefixes of the string. (For the empty prefix this
counter has value $0$). For the prefix consisting of one letter,
namely $b$, this counter has value $-1$ and for the prefix consisting
of the whole string it has value $1$. Hence by the mean value theorem
there is some prefix for which the counter takes value $0$. Let $p$ be
this prefix and let $q$ be the rest of the string. Note that $p$
starts with a $b$ and hence can be written as $b$ followed by $p'$.
Observe that both $p'$ and $q$ are strings of length less than $k+1$
with one more $a$ than $b$'s and, by the inductive hypothesis, are
generated by $A$. Hence if we first expand $A$ into $bAA$ and then
expand the first $A$ in $bAA$ into $p'$ and the second $A$ in $bAA$
into $q$ we get the whole string. The situation is similar for strings
of length $k+1$ with one more $b$ than $a$'s. Thus we have proven the
hypothesis for (odd) $k+1$.

\end{proof}


\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}

\end{document}




