\documentclass{article}

\input{macros}
\input{commands}

\begin{document}
\begin{center}\large\bf
CIS 570 --- Introduction to Formal Language Theory --- Fall 2006
\end{center}
\begin{center}\Large\bf
Exercise Set 1
\end{center}
\begin{center}\large\bf
Model Answers
\end{center}

\section*{Exercise 1}
\renewcommand{\thesection}{ES1.1}
\theoremnumber{1}

We proceed by mathematical induction.
\begin{description}
\item[\quad(Basis Step)] We have that
  $3(0^2 + 0 + 2) = 3\ast 2 = 6 = 6\ast 1$ and $1\in\nats$.

\item[\quad(Inductive Step)] Suppose $n\in\nats$, and
  assume the inductive hypothesis:
  \begin{displaymath}
    3(n^2 + n + 2) = 6m, \eqtxt{for some} m\in\nats .
  \end{displaymath}
  We must show that,
  \begin{displaymath}
    3((n+1)^2 + (n+1) + 2) = 6m, \eqtxt{for some} m\in\nats .
  \end{displaymath}
  We have that
  \begin{alignat*}{2}
    3((n + 1)^2 + (n + 1) + 2) &= 3(n^2 + 2n + 1) + 3(n + 1) + 6 \\
    &= 3n^2 + 6n + 3 + 3n + 3 + 6 \\
    &= 3n^2 + 3n + 6 + 6n + 6 \\
    &= 3(n^2 + n + 2) + 6(n + 1) \\
    &= 6m + 6(n + 1) && \by{inductive hypothesis} \\
    &= 6(m + n + 1) .
  \end{alignat*}
  Thus $3((n+1)^2 + (n+1) + 2) = 6(m + n + 1)$ and $m + n + 1\in\nats$.
\end{description}

\section*{Exercise 2}
\renewcommand{\thesection}{ES1.2}
\theoremnumber{1}

We proceed by strong induction.  Suppose $n\in\nats$, and assume the
inductive hypothesis: for all $m\in\nats$, if $m<n$, then,
\begin{displaymath}
  \eqtxtr{if} m\geq 18, \eqtxt{then
    there are} i,j\in\nats \eqtxt{such that}
  m = 4i + 7j .
\end{displaymath}
We must show that,
\begin{displaymath}
  \eqtxtr{if} n\geq 18, \eqtxt{then
    there are} i,j\in\nats \eqtxt{such that}
  n = 4i + 7j .
\end{displaymath}
Suppose $n\geq 18$.  We must show
that there are $i,j\in\nats$ such that $n = 4i + 7j$.  There are
five cases to consider.
\begin{itemize}
\item Suppose $n = 18$.  Then $n = 18 = 4\ast 1 + 7\ast 2$ and $1,2\in\nats$.
  
\item Suppose $n = 19$.  Then $n = 19 = 4\ast 3 + 7\ast 1$ and $3,1\in\nats$.
  
\item Suppose $n = 20$.  Then $n = 20 = 4\ast 5 + 7\ast 0$ and $5,0\in\nats$.
  
\item Suppose $n = 21$.  Then $n = 21 = 4\ast 0 + 7\ast 3$ and $0,3\in\nats$.
  
\item Suppose $n\geq 22$.  Thus $18 \leq n-4 < n$.  Because $n-4 < n$,
  the inductive hypothesis tells us that
  \begin{displaymath}
    \eqtxtr{if} n - 4\geq 18, \eqtxt{then
      there are} i,j\in\nats \eqtxt{such that}
    n - 4 = 4i + 7j .
  \end{displaymath}
  But $n - 4 \geq 18$, and thus $n - 4 = 4i + 7j$ for some $i,j\in\nats$.
  Hence
  \begin{displaymath}
    n = (n - 4) + 4 = 4i + 7j + 4 = 4(i + 1) + 7j ,
  \end{displaymath}
  and $i + 1, j\in\nats$.
\end{itemize}

\section*{Exercise 3}
\renewcommand{\thesection}{ES1.3}
\theoremnumber{1}

\textbf{(a)} Suppose $A$, $B$ and $C$ are sets.  We must show that
\begin{displaymath}
  A-(B\cup C) = (A - B) - C .
\end{displaymath}
It will suffice to show that
\begin{displaymath}
  A-(B\cup C) \sub (A - B) - C \sub A-(B\cup C) .
\end{displaymath}
\begin{description}
\item[\quad($A-(B\cup C) \sub (A - B) - C$)]
  Suppose $w\in A-(B\cup C)$.  We must show that $w\in (A - B) - C$.
  By the assumption, we have that $w\in A$ and $w\not\in(B\cup C)$.
  
  Suppose, toward a contradiction, that $w\in B$.  Then
  $w\in B\cup C$---contradiction.  Thus $w\not\in B$.
  
  Suppose, toward a contradiction, that $w\in C$.  Then
  $w\in B\cup C$---contradiction.  Thus $w\not\in C$.
  
  Because $w\in A$ and $w\not\in B$, we have that $w\in A-B$.
  Then, since $w\not\in C$, it follows that $w\in(A-B)-C$.
  
\item[\quad($(A - B) - C\sub A-(B\cup C)$)]
  Suppose $w\in (A - B) - C$.  We must show that $w\in A-(B\cup C)$.
  By the assumption, we have that $w\in A-B$ and $w\not\in C$.
  Hence $w\in A$ and $w\not\in B$.
  
  Suppose, toward a contradiction, that $w\in B\cup C$.  There are
  two cases to consider.
  \begin{itemize}
  \item Suppose $w\in B$.  But $w\not\in B$---contradiction.
    
  \item Suppose $w\in C$.  But $w\not\in C$---contradiction.
  \end{itemize}
  Since we obtained a contradiction in both cases, we have an overall
  contradiction.  Thus $w\not\in B\cup C$.
  
  Because $w\in A$ and $w\not\in B\cup C$, we have that $w\in A-(B\cup C)$.
\end{description}

\bigskip\noindent\textbf{(b)}
Suppose $A$, $B$ and $C$ are sets.  We must show that
\begin{displaymath}
  A - (B\cap C) = (A - B) \cup (A - C) .
\end{displaymath}
It will suffice to show that
\begin{displaymath}
  A - (B\cap C) \sub (A - B) \cup (A - C) \sub A - (B\cap C) .
\end{displaymath}
\begin{description}
\item[\quad($A - (B\cap C) \sub (A - B) \cup (A - C)$)]
  Suppose $w\in A - (B\cap C)$.  We must show that $w\in (A - B)\cup(A - C)$.
  By the assumption, we have that $w\in A$ and $w\not\in B\cap C$.
  There are two cases to consider.
  \begin{itemize}
  \item Suppose $w\in B$. Suppose, toward a contradiction, that $w\in C$.
    Thus $w\in B\cap C$---contradiction.  Thus $w\not\in C$.  And $w\in A$,
    and thus $w\in A-C \sub (A-B) \cup (A-C)$.
    
  \item Suppose $w\not\in B$.  Because $w\in A$, it follows that
    $w\in A-B \sub (A-B)\cup(A-C)$.
  \end{itemize}
  
\item[\quad($(A - B) \cup (A - C) \sub A - (B\cap C)$)]
  Suppose $w\in (A - B) \cup (A - C)$.  We must show that
  $w\in A - (B\cap C)$.  By the assumption, there are two cases to
  consider.
  \begin{itemize}
  \item Suppose $w\in A - B$.  Hence $w\in A$ and $w\not\in B$.
    Suppose, toward a contradiction, that $w\in B\cap C$.  Thus $w\in
    B$---contradiction.  Hence $w\not\in B\cap C$, so that
    $w\in A-(B\cap C)$.
    
  \item Suppose $w\in A - C$.  Hence $w\in A$ and $w\not\in C$.
    Suppose, toward a contradiction, that $w\in B\cap C$.  Thus $w\in
    C$---contradiction.  Hence $w\not\in B\cap C$, so that
    $w\in A-(B\cap C)$.
  \end{itemize}
\end{description}

\section*{Exercise 4}
\renewcommand{\thesection}{ES1.4}
\theoremnumber{1}

\textbf{(a)}\quad We use induction on $X$ to show that, for all $w\in
X$, $w\in Y$.  There are four steps to show.
\begin{enumerate}[\quad(1)]
\item Since $\diff(\%)=0$, we have that $\%\in Y$.
  
\item Suppose $w,x,y,z\in X$ and $w,x,y,z\in Y$.  We must show that
  $w\mathsf{1}x\mathsf{1}y\mathsf{0}z\in Y$.  Because $w,x,y,z\in Y$,
  it follows that $\diff(w)=\diff(x)=\diff(y)=\diff(z)=0$.
  Hence $\diff(w\mathsf{1}x\mathsf{1}y\mathsf{0}z) =
  \diff(w) + \diff(\mathsf{1}) + \diff(x) + \diff(\mathsf{1}) +
  \diff(y) + \diff(\mathsf{0}) + \diff(z) =
  0 + 1 + 0 + 1 + 0 + -2 + 0 = 0$, showing that
  $w\mathsf{1}x\mathsf{1}y\mathsf{0}z\in Y$.
  
\item Suppose $w,x,y,z\in X$ and $w,x,y,z\in Y$.  We must show that
  $w\mathsf{1}x\mathsf{0}y\mathsf{1}z\in Y$.  Because $w,x,y,z\in Y$,
  it follows that $\diff(w)=\diff(x)=\diff(y)=\diff(z)=0$.
  Hence $\diff(w\mathsf{1}x\mathsf{0}y\mathsf{1}z) =
  \diff(w) + \diff(\mathsf{1}) + \diff(x) + \diff(\mathsf{0}) +
  \diff(y) + \diff(\mathsf{1}) + \diff(z) =
  0 + 1 + 0 + -2 + 0 + 1 + 0 = 0$, showing that
  $w\mathsf{1}x\mathsf{0}y\mathsf{1}z\in Y$.
  
\item Suppose $w,x,y,z\in X$ and $w,x,y,z\in Y$.  We must show that
  $w\mathsf{0}x\mathsf{1}y\mathsf{1}z\in Y$.  Because $w,x,y,z\in Y$,
  it follows that $\diff(w)=\diff(x)=\diff(y)=\diff(z)=0$.
  Hence $\diff(w\mathsf{0}x\mathsf{1}y\mathsf{1}z) =
  \diff(w) + \diff(\mathsf{0}) + \diff(x) + \diff(\mathsf{1}) +
  \diff(y) + \diff(\mathsf{1}) + \diff(z) =
  0 + -2 + 0 + 1 + 0 + 1 + 0 = 0$, showing that
  $w\mathsf{0}x\mathsf{1}y\mathsf{1}z\in Y$.
\end{enumerate}

\medskip\noindent\textbf{(b)} We begin by proving two lemmas.

\begin{lemma}
\label{Ex4Lem1}
For all $w\in\{\mathsf{0,1}\}^*$, if $\diff(w)\geq 1$, then
there are $x,y\in\{\mathsf{0,1}\}^*$ such that $w=x\onesf y$,
$\diff(x)=0$ and $\diff(y) = \diff(w) - 1$.
\end{lemma}

\begin{proof}
Suppose $w\in\{\mathsf{0,1}\}^*$ and suppose $\diff(w)\geq 1$.
Let $z$ be the shortest prefix of $w$ such that $\diff(z)\geq 1$.
(Such a $z$ exists, because $w$ is a prefix of itself with a positive
diff.)  Let $y\in\{\mathsf{0,1}\}^*$ be such that $w=zy$.
Because $\diff(z)\geq 1$, we have that $z\neq\%$.  Thus
$z=xb$, for some $x\in\{\mathsf{0,1}\}^*$ and $b\in\{\mathsf{0,1}\}$.
Because $x$ is a shorter prefix of $w$ than $z$, it follows that
$\diff(x)\leq 0$.

Suppose, toward a contradiction, that $b=\zerosf$.  Since
$\diff(x) + -2 = \diff(x\zerosf) = \diff(xb) = \diff(z)\geq 1$,
we have that $\diff(x)\geq 3$---contradiction.  Thus $b=\onesf$,
so that $z=xb=x\onesf$ and $w=zy=x\onesf y$.

Since $\diff(x)+1=\diff(x\onesf)=\diff(z)\geq 1$, we have that
$\diff(x)\geq 0$.  But $\diff(x)\leq 0$, and thus $\diff(x)=0$.
And, because $1 + \diff(y) = 0 + 1 + \diff(y) = \diff(x1y) = \diff(w)$,
we have that $\diff(y) = \diff(w) - 1$.
\end{proof}

\begin{lemma}
\label{Ex4Lem2}
For all $w\in\{\mathsf{0,1}\}^*$, if $\diff(w)\leq -1$, then
there are $x,y\in\{\mathsf{0,1}\}^*$ such that $w=x\zerosf y$,
and either
\begin{itemize}
\item $\diff(x) = 0$ and $\diff(y) = \diff(w) + 2$; or
  
\item $\diff(x) = 1$ and $\diff(y) = \diff(w) + 1$.
\end{itemize}
\end{lemma}

\begin{proof}
Suppose $w\in\{\mathsf{0,1}\}^*$ and suppose $\diff(w)\leq -1$.
Let $z$ be the shortest prefix of $w$ such that $\diff(z)\leq -1$.
(Such a $z$ exists, because $w$ is a prefix of itself with a negative
diff.)  Let $y\in\{\mathsf{0,1}\}^*$ be such that $w=zy$.
Because $\diff(z)\leq -1$, we have that $z\neq\%$.  Thus
$z=xb$, for some $x\in\{\mathsf{0,1}\}^*$ and $b\in\{\mathsf{0,1}\}$.
Because $x$ is a shorter prefix of $w$ than $z$, it follows that
$\diff(x)\geq 0$.

Suppose, toward a contradiction, that $b=\onesf$.  Since
$\diff(x) + 1 = \diff(x\onesf) = \diff(xb) = \diff(z)\leq -1$,
we have that $\diff(x)\leq -2$---contradiction.  Thus $b=\zerosf$,
so that $z=xb=x\zerosf$ and $w=zy=x\zerosf y$.

Since $\diff(x)+-2=\diff(x\zerosf)=\diff(z)\leq -1$, we have that
$\diff(x)\leq 1$.  But $\diff(x)\geq 0$, and thus $\diff(x)\in\{0,1\}$.
Thus there are two cases to consider.
\begin{itemize}
\item Suppose $\diff(x)=0$.  Because $-2 + \diff(y) = 0 + -2 +
  \diff(y) = \diff(x\zerosf y) = \diff(w)$, we have that $\diff(y) =
  \diff(w) + 2$.  Thus $\diff(x)=0$ and $\diff(y) = \diff(w) + 2$.
  
\item Suppose $\diff(x)=1$.  Because $-1 + \diff(y) = 1 + -2 +
  \diff(y) = \diff(x\zerosf y) = \diff(w)$, we have that $\diff(y) =
  \diff(w) + 1$.  Thus $\diff(x)=1$ and $\diff(y) = \diff(w) + 1$.
\end{itemize}
\end{proof}

Now, we show that $Y\sub X$.  Since $Y\sub\{\mathsf{0,1}\}^*$, it will
suffice to show that, for all $w\in\{\mathsf{0,1}\}^*$,
\begin{displaymath}
  \eqtxtr{if}w\in Y,\eqtxt{then}w\in X .
\end{displaymath}
We proceed by strong string induction.
Suppose
$w\in\{\mathsf{0,1}\}^*$, and assume the inductive hypothesis: for all
$x\in \{\mathsf{0,1}\}^*$, if $|x|<|w|$, then
\begin{displaymath}
  \eqtxtr{if}x\in Y,\eqtxt{then}x\in X .
\end{displaymath}
We must show that
\begin{displaymath}
  \eqtxtr{if}w\in Y,\eqtxt{then}w\in X .
\end{displaymath}
Suppose $w\in Y$, so that $\diff(w)=0$.  We must show that $w\in X$.
There are three cases to consider.

\begin{itemize}
\item Suppose $w=\%$.  Then $w=\%\in X$, by Part~(1) of the definition of $X$.
  
\item Suppose $w=\zerosf s$, for some $s\in\{\mathsf{0,1}\}^*$.
  Because $-2 + \diff(s) = \diff(\zerosf s) =
  \diff(w) = 0$, we have that $\diff(s) = 2$.
  Since $\diff(s)\geq 1$, Lemma~\ref{Ex4Lem1} tells us that there are
  $x,t\in\{\mathsf{0,1}\}^*$ such that $s=x\onesf t$, $\diff(x) = 0$
  and $\diff(t) = \diff(s) - 1$.  Hence $x\in Y$ and $\diff(t) = 2 - 1
  = 1$.  Since $\diff(t)\geq 1$, Lemma~\ref{Ex4Lem1} tells us that
  there are $y,z\in\{\mathsf{0,1}\}^*$ such that $t=y\onesf z$,
  $\diff(y) = 0$ and $\diff(z) = \diff(t) - 1$.  Hence $y\in Y$ and
  $\diff(z) = 1 - 1 = 0$, so that $z\in Y$.  Summarizing, we have that
  $w=\zerosf s=\zerosf x\onesf t= \zerosf x\onesf y\onesf z$ and
  $x,y,z\in Y$.  Because $|x|<|w|$, $|y|<|w|$ and $|z|<|w|$, the
  inductive hypothesis tells us that $x,y,z\in X$.  By Part~(1) of the
  definition on $X$, we have that $\%\in X$.  Finally, since
  $\%,x,y,z\in X$, Part~(4) of the definition of $X$ tells us that $w
  = \zerosf x\onesf y\onesf z = \%\zerosf x\onesf y\onesf z\in X$.
  
\item Suppose $w=\onesf s$, for some $s\in\{\mathsf{0,1}\}^*$.
  Because $1 + \diff(s) = \diff(\onesf s) =
  \diff(w) = 0$, we have that $\diff(s) = -1$.
  Since $\diff(s)\leq -1$, Lemma~\ref{Ex4Lem2} tells us that there are
  $x,y\in\{\mathsf{0,1}\}^*$ such that $s=x\zerosf y$, and either
  \begin{itemize}
  \item $\diff(x) = 0$ and $\diff(y) = \diff(s) + 2$; or
    
  \item $\diff(x) = 1$ and $\diff(y) = \diff(s) + 1$.
  \end{itemize}
  Thus there are two cases to consider.
  \begin{itemize}
  \item Suppose $\diff(x) = 0$ and $\diff(y) = \diff(s) + 2$.  Hence
    $x\in Y$ and $\diff(y) = -1 + 2 = 1$.  Since $\diff(y)\geq 1$,
    Lemma~\ref{Ex4Lem1} tells us that there are
    $z,t\in\{\mathsf{0,1}\}^*$ such that $y=z\onesf t$, $\diff(z) = 0$
    and $\diff(t) = \diff(y) - 1$.  Hence $z\in Y$ and $\diff(t) = 1 -
    1 = 0$, so that $t\in Y$.  Summarizing, we have that $w = \onesf s
    = \onesf x\zerosf y = \onesf x\zerosf z\onesf t$ and $x,z,t\in Y$.
    Because $|x|<|w|$, $|z|<|w|$ and $|t|<|w|$, the inductive hypothesis
    tells us that $x,z,t\in X$.  By Part~(1) of the definition on $X$,
    we have that $\%\in X$.  Finally, since $\%,x,z,t\in X$, Part~(3)
    of the definition of $X$ tells us that $w = \onesf x\zerosf
    z\onesf t = \%\onesf x\zerosf z\onesf t\in X$.
    
  \item Suppose $\diff(x) = 1$ and $\diff(y) = \diff(s) + 1$.  Hence
    $\diff(y) = -1 + 1 = 0$, so that $y\in Y$.  Since $\diff(x)\geq
    1$, Lemma~\ref{Ex4Lem1} tells us that there are
    $z,t\in\{\mathsf{0,1}\}^*$ such that $x=z\onesf t$, $\diff(z) = 0$
    and $\diff(t) = \diff(x) - 1$.  Hence $z\in Y$ and $\diff(t) = 1 -
    1 = 0$, so that $t\in Y$.  Summarizing, we have that $w = \onesf s
    = \onesf x\zerosf y = \onesf z\onesf t\zerosf y$ and $z,t,y\in Y$.
    Because $|z|<|w|$, $|t|<|w|$ and $|y|<|w|$, the inductive hypothesis
    tells us that $z,t,y\in X$.  By Part~(1) of the definition on $X$,
    we have that $\%\in X$.  Finally, since $\%,z,t,y\in X$, Part~(2)
    of the definition of $X$ tells us that $w = \onesf z\onesf
    t\zerosf y = \%\onesf z\onesf t\zerosf y\in X$.
  \end{itemize}
\end{itemize}
\end{document}