\documentclass{article}
\usepackage{charter}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[T1]{fontenc}
\usepackage{listings}
\usepackage{xcolor}

\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}%

\definecolor{javared}{rgb}{0.6,0,0} % for strings
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc

\lstdefinelanguage{scala}{
  morekeywords={abstract,case,catch,class,def,%
    do,else,extends,false,final,finally,%
    for,if,implicit,import,match,mixin,%
    new,null,object,override,package,%
    private,protected,requires,return,sealed,%
    super,this,throw,trait,true,try,%
    type,val,var,while,with,yield},
  otherkeywords={=>,<-,<\%,<:,>:,\#,@},
  sensitive=true,
  morecomment=[l]{//},
  morecomment=[n]{/*}{*/},
  morestring=[b]",
  morestring=[b]',
  morestring=[b]"""
}

\lstset{language=Scala,
	basicstyle=\ttfamily,
	keywordstyle=\color{javapurple}\bfseries,
	stringstyle=\color{javagreen},
	commentstyle=\color{javagreen},
	morecomment=[s][\color{javadocblue}]{/**}{*/},
	numbers=left,
	numberstyle=\tiny\color{black},
	stepnumber=1,
	numbersep=10pt,
	tabsize=2,
	showspaces=false,
	showstringspaces=false}
	
\begin{document}

\section*{Handout 2}

Having specified what problem our matching algorithm, $match$, is supposed to solve, namely
for a given regular expression $r$ and string $s$ answer $true$ if and only if

\[
s \in L(r)
\]

\noindent
Clearly we cannot use the function $L$ directly in order to solve this problem, because in general
the set of strings $L$ returns is infinite (recall what $L(a^*)$ is). In such cases there is no algorithm
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 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}

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