# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1380898542 -3600
# Node ID dd8b5a3dac0a4be1428ed65261343a8273f3d9cc
# Parent  a75f9c9d8f940adef215f8f280f4244e7db6ce2a
adde

diff -r a75f9c9d8f94 -r dd8b5a3dac0a handouts/ho02.pdf
Binary file handouts/ho02.pdf has changed
diff -r a75f9c9d8f94 -r dd8b5a3dac0a handouts/ho02.tex
--- a/handouts/ho02.tex	Fri Oct 04 15:40:10 2013 +0100
+++ b/handouts/ho02.tex	Fri Oct 04 15:55:42 2013 +0100
@@ -62,9 +62,35 @@
 then can test exhaustively, whether a string is member of this set.
 
 The algorithm we define below consists of two parts. One is the function $nullable$ which takes a
-regular expression as argument and decides whether it can match the empty string. This can be easily 
-defined recursively as follows:
+regular expression as argument and decides whether it can match the empty string (this means it returns a 
+boolean). This can be easily defined recursively as follows:
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+$nullable(\varnothing)$      & $\dn$ & $f\!\/alse$\\
+$nullable(\epsilon)$           & $\dn$ &  $true$\\
+$nullable (c)$                    & $\dn$ &  $f\!alse$\\
+$nullable (r_1 + r_2)$       & $\dn$ &  $nullable(r_1) \vee nullable(r_2)$\\ 
+$nullable (r_1 \cdot r_2)$ & $\dn$ &  $nullable(r_1) \wedge nullable(r_2)$\\
+$nullable (r^*)$                & $\dn$ & $true$ \\
+\end{tabular}
+\end{center}
 
+\noindent
+The idea behind this function is that the following property holds:
+
+\[
+nullable(r) \;\;\text{if and only if}\;\; ""\in L(r)
+\]
+
+\noindent
+On the left-hand side we have a function we can implement; on the right we have its specification. 
+
+The other function is calculating a \emph{derivative} of a regular expression. This is a function
+which will take a regular expression, say $r$, and a character, say $c$, as argument and return 
+a new regular expression. Beware that the intuition behind this function is not so easy to grasp on first
+reading. Essentially this function solves the following problem: if $r$ can match a string of the form
+$c\!::\!s$, what does the regular expression look like that can match just $s$.
 
 \end{document}