\documentclass[12pt]{article}   
\usepackage{latex-macros/course}% !! Use the macros

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip
                                % query 


\begin{document}


\begin{problem} \textbf{Structural Induction}

%This Intro is copied from Problem Set 5

Suppose we start with a sequence of fully parenthesized arithmetic or
Scheme expressions, and then erase all the alphanumeric characters other
than parentheses.  The result is a string of parentheses which ``match
up''.

For example, erasing non-parenthesis characters from the expression
\texttt{(if (or x y) u v)} leaves the string \texttt{(())}.  Similarly,
erasing non-parentheses from the sequence of three arithmetic expressions
\[
\texttt{(x * x), (y + (3 * (z - 9))), ((x + y) * (u + w))}
\]
leaves the string
\[
\texttt{()((()))(()())}.
\]
On the other hand, even though the string \texttt{())(()} has an equal
number of left and right parentheses, it cannot be obtained by erasing in
this way---because the two middle parentheses don't match up.  Also, no
string of parentheses which begins with a right parenthesis or ends with a
left parenthesis can match up.

We gave an inductive definition of the set, SMU, of ``Strings which
Match Up'' in Problem Set 5, as follows:

\begin{itemize}
\item The empty string (consisting of no parentheses) is an SMU.

\item If $s$ and $t$ are SMU's, then the string $\texttt{(}s\texttt{)}t$
is an SMU.  That is, the new string starts with a left parenthesis which
is followed by the parenthesis characters in the string $s$, followed by a
right parenthesis, followed by the parenthesis characters in the string
$t$.

\end{itemize}


% New Problem Starts here:

Consider the following sets of strings of parentheses:

\newcommand{\SMU}{\textrm{SMU}}

a) Set $A$
\begin{itemize} 
\item The empty string $\lambda$ is in  $A$.
\item if $s$ is  in $A$, then $\texttt{(}s\texttt{)}$ 
is in $A$.
\item if $s$ and $t$ are in $A$, then $st$ is in $A$.
\end{itemize}

b) Set $B$
\begin{itemize} 
\item The empty string $\lambda$ is in  $B$.
\item if $s$ is  in $B$, then $\texttt{(}s\texttt{)}$  is in $B$.
\item if $s$ and $t$ are in $B$, then $(st)$ is in $B$.
\end{itemize}

c) Set $C$
\begin{itemize} 
\item The empty string $\lambda$ is in  $C$.
\item if $s$ and $t$ are in $C$, then $\texttt{(}s\texttt{)(}t\texttt{)}$ is in $C$.
\end{itemize}

d) Set $D$ 
Starting with zero, read the string from left to right adding one for
each left parenthesis and -1 for each right parenthesis.  A string
\emph{counts pretty well} when the count is 
 back to zero by the end  of the string.
Let $D$ be the set of strings of parentheses which Count Pretty Well.

e) Set $E$
\begin{itemize} 
\item The empty string $\lambda$ is in  $E$.
\item if $s$ is  in $E$, then $\texttt{(}s\texttt{)}$ is in $E$.
\item if $s$ and $t$ are in $E$, then $st\texttt{)}$ is in $E$.
\end{itemize}

f) Set $F=D \cap E$.

Part I:
For each of the sets $X\in \{A,B,C,D\}$, determine whether
$X=\SMU$. If $X\neq \SMU$ then
give a string $w$ of shortest length that serves as a counterexample
to the claim $X=\SMU$.


Solution:
Set $A$:  $A=\SMU$ 
 
Set $B$:  Shortest Counter-Example: ()()

Set $C$:  Shortest Counter-Example: ()

Set $D$:  Shortest Counter-Example: )(

Set $E$:  Shortest Counter-Example: )

Set $F$:  Shortest Counter-Example: ()()

Part II:
Now we would like to prove that $A\subset \SMU$ by structural induction.
Among the following statements, circle the best candidate for 
the induction  hypothesis.

\[
P(s) ::\equiv s \in \SMU
\]
\[
P(s) ::\equiv s \in A
\]
\[
P(s) ::\equiv \forall s \in A  \left(s \in \SMU\right)
\]
\[
P(s) ::\equiv \forall s \in \SMU \left(s \in A\right)
\]



\end{problem}



\end{document}

