\problemdata     
{induction-7}           
{structural induction}              
{}              
{S01-PS2} 		
{S01 Karger}        	



\begin{problem} 


The set $W$ of ``well-formed parenthesis strings'' can be defined by
the following rules:

\vspace*{-0.5\baselineskip}

\begin{enumerate}\itemsep 0\baselineskip
\item the empty string is in $W$, and
\item if $s$ and $t$ are in W then the string $(s)t$ is in $W$.
\end{enumerate}
For example, the string $(()())()$ is a well-formed parenthesis
string, where as the string $)(())$, isn't.

Use structural induction to prove that any prefix of any well-formed
parenthesis string has at least as many left parentheses as right
parentheses.

\solution{


  Let $P(t)$, for $t \in W$, be the predicate that any prefix of a
  well-formed parenthesis string $t$ has at least as many left as
  right parentheses.  We prove that $P(t)$ holds for all $t \in W$ by
  structural induction.

  \begin{description}\itemsep 0\baselineskip
  \item[Base Case:] \mbox{} \\ %
    Let $t$ be the empty string $\lambda$.  $P(\lambda)$ holds since
    there are no left or right parentheses.

  \item[Inductive Step:] \mbox{} \\ %
    We must show that for all $s, t \in W$, $P(s)$ and $P(t)$ imply
    $P((s)t)$; that is, that any prefix of the string $(s)t$ has at
    least as many left as right parentheses.  Let $s, t$ be any
    strings in $W$ and assume that $P(s)$ and $P(t)$ hold.  Moreover,
    for any $s_1$ and $s_2$, let $s_1 \leq s_2$ denote that $s_1$ is a
    prefix of the string $s_2$.  Let $p$ be any prefix of the string
    $(s)t$ and consider the following set of exhaustive cases:

    \begin{description}\itemsep 0\baselineskip
    \item[$p = \lambda$] \mbox{} \\ %
      In this case, $p$ trivially satisfies the claim.

    \item[$p = ($] \mbox{} \\ %
      In this case, $p$ trivially satisfies the claim.

    \item[$p = (s'$, for some string $s'$, $s' \leq s$] \mbox{} \\ %
      In this case, since $P(s)$ holds, it follows that $s'$ has at
      least as many left as right parentheses.  Thus, the same
      property holds for the string $(s'$.

    \item[$p = (s)$] \mbox{} \\ %
      In this case, since $P(s)$ holds, the string $(s)$ has at least
      as many left as right parentheses.

    \item[$p = (s)t'$, for some string $t'$, $t' \leq t$] \mbox{} \\ %
      In this case, by the previous case, we know that the string
      $(s)$ has at least as many left as right parentheses.  Moreover,
      since $P(t)$ holds, it follows that $t'$ has at least as many
      left as right parentheses.  Thus, it follows that the string
      $(s)t'$ has at least as many left as right parentheses.
    \end{description}

    Thus, any prefix of $(s)t$ has at least as many left as right
    parentheses; that is, $P((s)t)$ holds.  Finally, by universal
    generalization, the inductive step holds for any such $s, t \in
    W$.

  \end{description}

}

\end{problem}





