--- a/hws/proof.tex Wed Apr 06 15:55:01 2016 +0100
+++ b/hws/proof.tex Fri May 06 13:15:52 2016 +0100
@@ -1,10 +1,6 @@
\documentclass{article}
-\usepackage{charter}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
+\usepackage{../style}
-\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
\begin{document}
\section*{Proof}
@@ -14,16 +10,16 @@
\begin{center}
\begin{tabular}{c}
\begin{tabular}[t]{rcl}
- $r$ & $::=$ & $\varnothing$ \\
- & $\mid$ & $\epsilon$ \\
+ $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(\varnothing)$ & $\dn$ & $\varnothing$ \\
-$L(\epsilon)$ & $\dn$ & $\{\texttt{""}\}$ \\
+$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)$ \\
@@ -37,9 +33,9 @@
\begin{center}
\begin{tabular}{lcl}
- $der\, c\, (\varnothing)$ & $\dn$ & $\varnothing$ \\
- $der\, c\, (\epsilon)$ & $\dn$ & $\varnothing$ \\
- $der\, c\, (d)$ & $\dn$ & if $c = d$ then $\epsilon$ else $\varnothing$\\
+ $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)$\\
@@ -53,7 +49,7 @@
regular expressions. We can establish that $\forall r.\; P(r)$ holds, provided we can show the following:
\begin{enumerate}
-\item $P(\varnothing)$, $P(\epsilon)$ and $P(c)$ all hold,
+\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
@@ -86,25 +82,25 @@
{\bf Proof}
\noindent
-According to 1.~above we need to prove $P(\varnothing)$, $P(\epsilon)$ and $P(d)$. Lets do this in turn.
+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(\varnothing)$ is $L(der\,c\,\varnothing) = Der\,c\,(L(\varnothing))$ (a). We have $der\,c\,\varnothing = \varnothing$
-and $L(\varnothing) = \varnothing$. We also have $Der\,c\,\varnothing = \varnothing$. Hence we have $\varnothing = \varnothing$ in (a).
+\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(\epsilon)$ is $L(der\,c\,\epsilon) = Der\,c\,(L(\epsilon))$ (b). We have $der\,c\,\epsilon = \varnothing$,
-$L(\varnothing) = \varnothing$ and $L(\epsilon) = \{\texttt{""}\}$. We also have $Der\,c\,\{\texttt{""}\} = \varnothing$. Hence we have
-$\varnothing = \varnothing$ in (b).
+\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 = \epsilon$ and $L(\epsilon) = \{\texttt{""}\}$.
+$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 = \varnothing$.
-We also have $Der\,c\,\{\texttt{"}d\texttt{"}\} = \varnothing$. Hence we have
-$\varnothing = \varnothing$ 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
@@ -196,7 +192,7 @@
$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) = \varnothing$.
+The first union ``disappears'' since $Der\,c\,(L(r)^0) = \ZERO$.
\end{document}