\documentclass{article}
\usepackage{../style}

\begin{document}

\section*{Proof}

Recall the definitions for regular expressions and the language associated with a regular expression:

\begin{center}
\begin{tabular}{c}
\begin{tabular}[t]{rcl}
  $r$ & $::=$  & $\ZERO$  \\
         & $\mid$ & $\ONE$       \\
         & $\mid$ & $c$                         \\
         & $\mid$ & $r_1 \cdot r_2$ \\
         & $\mid$ & $r_1 + r_2$  \\
         & $\mid$ & $r^*$                 \\
  \end{tabular}\hspace{10mm}
\begin{tabular}[t]{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
$L(\ZERO)$ & $\dn$ & $\varnothing$ \\
$L(\ONE)$       & $\dn$ & $\{\texttt{""}\}$       \\
$L(c)$                   & $\dn$ & $\{\texttt{"}c\texttt{"}\}$                         \\
$L(r_1 \cdot r_2)$   & $\dn$ & $L(r_1) \,@\, L(r_2)$ \\
$L(r_1 + r_2)$         & $\dn$ & $L(r_1) \cup L(r_2)$  \\
 $L(r^*)$        & $\dn$ & $\bigcup_{n\ge 0} L(r)^n$                 \\
  \end{tabular}
\end{tabular}
\end{center}

\noindent
We also defined the notion of a derivative of a regular expression (the derivative with respect to a character):

\begin{center}
\begin{tabular}{lcl}
  $der\, c\, (\ZERO)$    & $\dn$ & $\ZERO$  \\
  $der\, c\, (\ONE)$          & $\dn$ & $\ZERO$ \\
  $der\, c\, (d)$                      & $\dn$ & if $c = d$ then $\ONE$ else $\ZERO$\\
  $der\, c\, (r_1 + r_2)$        & $\dn$ & $(der\, c\, r_1) + (der\, c\, r_2)$ \\
  $der\, c\, (r_1 \cdot r_2)$ & $\dn$  & if $nullable(r_1)$\\
       & & then $((der\, c\, r_1) \cdot r_2) + (der\, c\, r_2)$\\ 
       & & else $(der\, c\, r_1) \cdot r_2$\\
  $der\, c\, (r^*)$                   & $\dn$ & $(der\, c\, r) \cdot (r^*)$\\
  \end{tabular}
\end{center}

\noindent
With our definition of regular expressions comes an induction principle. Given a property $P$ over 
regular expressions. We can establish that $\forall r.\; P(r)$ holds, provided we can show the following:

\begin{enumerate}
\item $P(\ZERO)$, $P(\ONE)$ and $P(c)$ all hold,
\item $P(r_1 + r_2)$ holds under the induction hypotheses that 
$P(r_1)$ and $P(r_2)$ hold,
\item $P(r_1 \cdot r_2)$ holds under the induction hypotheses that 
$P(r_1)$ and $P(r_2)$ hold, and
\item $P(r^*)$ holds under the induction hypothesis that $P(r)$ holds.
\end{enumerate}

\noindent
Let us try out an induction proof. Recall the definition

\begin{center}
$Der\, c\, A \dn \{ s\;\mid\; c\!::\!s \in A\}$
\end{center}

\noindent
whereby $A$ is a set of strings. We like to prove

\begin{center}
\begin{tabular}{l}
$P(r) \dn $ \hspace{4mm} $L(der\,c\,r) = Der\,c\,(L(r))$
\end{tabular}
\end{center}

\noindent
by induction over the regular expression $r$.


\newpage
\noindent
{\bf Proof}

\noindent
According to 1.~above we need to prove $P(\ZERO)$, $P(\ONE)$ and $P(d)$. Lets do this in turn.

\begin{itemize}
\item First Case: $P(\ZERO)$ is $L(der\,c\,\ZERO) = Der\,c\,(L(\ZERO))$ (a). We have $der\,c\,\ZERO = \ZERO$ 
and $L(\ZERO) = \ZERO$. We also have $Der\,c\,\ZERO = \ZERO$. Hence we have $\ZERO = \ZERO$ in (a). 

\item Second  Case: $P(\ONE)$ is $L(der\,c\,\ONE) = Der\,c\,(L(\ONE))$ (b). We have $der\,c\,\ONE = \ZERO$,
$L(\ZERO) = \ZERO$ and $L(\ONE) = \{\texttt{""}\}$. We also have $Der\,c\,\{\texttt{""}\} = \ZERO$. Hence we have 
$\ZERO = \ZERO$ in (b). 

\item Third  Case: $P(d)$ is $L(der\,c\,d) = Der\,c\,(L(d))$ (c). We need to treat the cases $d = c$ and $d \not= c$. 

$d = c$: We have $der\,c\,c = \ONE$ and $L(\ONE) = \{\texttt{""}\}$. 
We also have $L(c) = \{\texttt{"}c\texttt{"}\}$ and $Der\,c\,\{\texttt{"}c\texttt{"}\} = \{\texttt{""}\}$. Hence we have 
$\{\texttt{""}\} = \{\texttt{""}\}$ in (c). 

$d \not=c$: We have $der\,c\,d = \ZERO$.
We also have $Der\,c\,\{\texttt{"}d\texttt{"}\} = \ZERO$. Hence we have 
$\ZERO = \ZERO$  in (c). 
\end{itemize}

\noindent
These were the easy base cases. Now come the inductive cases.

\begin{itemize}
\item Fourth Case: $P(r_1 + r_2)$ is $L(der\,c\,(r_1 + r_2)) = Der\,c\,(L(r_1 + r_2))$ (d). This is what we have to show.
We can assume already:

\begin{center}
\begin{tabular}{ll}
$P(r_1)$: & $L(der\,c\,r_1) = Der\,c\,(L(r_1))$ (I)\\
$P(r_2)$: & $L(der\,c\,r_2) = Der\,c\,(L(r_2))$ (II)
\end{tabular}
\end{center}

We have that $der\,c\,(r_1 + r_2) = (der\,c\,r_1) + (der\,c\,r_2)$ and also $L((der\,c\,r_1) + (der\,c\,r_2)) = L(der\,c\,r_1) \cup L(der\,c\,r_2)$.
By (I) and (II) we know that the left-hand side is $Der\,c\,(L(r_1)) \cup Der\,c\,(L(r_2))$.  You need to ponder a bit, but you should see
that 

\begin{center}
$Der\,c(A \cup B) = (Der\,c\,A) \cup (Der\,c\,B)$
\end{center}

holds for every set of strings $A$ and $B$. That means the right-hand side of (d) is also $Der\,c\,(L(r_1)) \cup Der\,c\,(L(r_2))$,
because $L(r_1 + r_2) = L(r_1) \cup L(r_2)$. And we are done with the fourth case.
 
\item Fifth Case: $P(r_1 \cdot r_2)$ is $L(der\,c\,(r_1 \cdot r_2)) = Der\,c\,(L(r_1 \cdot r_2))$ (e). We can assume already:

\begin{center}
\begin{tabular}{ll}
$P(r_1)$: & $L(der\,c\,r_1) = Der\,c\,(L(r_1))$ (I)\\
$P(r_2)$: & $L(der\,c\,r_2) = Der\,c\,(L(r_2))$ (II)
\end{tabular}
\end{center}

Let us first consider the case where $nullable(r_1)$ holds. Then 

\[
der\,c\,(r_1 \cdot r_2) = ((der\,c\,r_1) \cdot r_2) + (der\,c\,r_2).
\]

The corresponding language of the right-hand side is 

\[
(L(der\,c\,r_1) \,@\, L(r_2)) \cup L(der\,c\,r_2).
\]

By the induction hypotheses (I) and (II), this is equal to

\[
(Der\,c\,(L(r_1)) \,@\, L(r_2)) \cup (Der\,c\,(L(r_2)).\;\;(**)
\]

We also know that $L(r_1 \cdot r_2) = L(r_1) \,@\,L(r_2)$.  We have to know what
$Der\,c\,(L(r_1) \,@\,L(r_2))$ is.

Let us analyse what
$Der\,c\,(A \,@\, B)$ is for arbitrary sets of strings $A$ and $B$. If $A$ does \emph{not}
contain the empty string, then every string in $A\,@\,B$ is of the form $s_1 \,@\, s_2$ where
$s_1 \in A$ and $s_2 \in B$. So if $s_1$ starts with $c$ then we just have to remove it. Consequently,
$Der\,c\,(A \,@\, B) = (Der\,c\,(A)) \,@\, B$. This case does not apply here though, because we already 
proved that if $r_1$ is nullable, then $L(r_1)$ contains the empty string. In this case, every string
in  $A\,@\,B$ is either of the form $s_1 \,@\, s_2$, with $s_1 \in A$ and $s_2 \in B$, or
$s_3$ with $s_3 \in B$. This means $Der\,c\,(A \,@\, B) = ((Der\,c\,(A)) \,@\, B) \cup Der\,c\,B$.
But this proves that (**) is $Der\,c\,(L(r_1) \,@\, L(r_2))$.

Similarly in the case where $r_1$ is \emph{not} nullable.

\item Sixth Case: $P(r^*)$ is $L(der\,c\,(r^*)) = Der\,c\,L(r^*)$. We can assume already:

\begin{center}
\begin{tabular}{ll}
$P(r)$: & $L(der\,c\,r) = Der\,c\,(L(r))$ (I)
\end{tabular}
\end{center}

We have $der\,c\,(r^*) = der\,c\,r\cdot r^*$. Which means $L(der\,c\,(r^*)) = L(der\,c\,r\cdot r^*)$ and
further $L(der\,c\,r) \,@\, L(r^*)$. By induction hypothesis (I) we know that is equal to 
$(Der\,c\,L(r)) \,@\, L(r^*)$. (*)

\end{itemize}

Let us now analyse $Der\,c\,L(r^*)$, which is equal to $Der\,c\,((L(r))^*)$. Now $(L(r))^*$ is defined
as $\bigcup_{n \ge 0} L(r)^n$. We can write this as $L(r)^0 \cup \bigcup_{n \ge 1} L(r)^n$, where we just 
separated the first union and then let the ``big-union'' start from $1$. Form this we can already infer

\begin{center}
$Der\,c\,(L(r^*)) = Der\,c\,(L(r)^0 \cup \bigcup_{n \ge 1} L(r)^n) = (Der\,c\,L(r)^0) \cup Der\,c\,(\bigcup_{n \ge 1} L(r)^n)$
\end{center}

The first union ``disappears'' since $Der\,c\,(L(r)^0) = \ZERO$.


\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: