# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1411947938 -3600
# Node ID 92e6985018ae12892f750d5fc07bd4043b34b80f
# Parent  ee4304bc6350096668dd8399e572a59ddb4ba2f2
updated

diff -r ee4304bc6350 -r 92e6985018ae handouts/ho02.pdf
Binary file handouts/ho02.pdf has changed
diff -r ee4304bc6350 -r 92e6985018ae handouts/ho02.tex
--- a/handouts/ho02.tex	Sun Sep 28 22:30:25 2014 +0100
+++ b/handouts/ho02.tex	Mon Sep 29 00:45:38 2014 +0100
@@ -4,7 +4,7 @@
 \usepackage{../graphics}
 \usepackage{../data}
 
-
+\pgfplotsset{compat=1.11}
 \begin{document}
 
 \section*{Handout 2}
@@ -14,9 +14,9 @@
 than the matchers from regular expression libraries in Ruby and
 Python (the plots on the left). These plots show the running 
 time for the evil regular expression $a?^{\{n\}}a^{\{n\}}$.
-Note the different scales in each plot.
+Note the different scales of the $x$-axes. 
 
-\pgfplotsset{compat=1.11}
+
 \begin{center}
 \begin{tabular}{@{}cc@{}}
 \begin{tikzpicture}
\begin{axis}[
    xlabel={\pcode{a}s},
    ylabel={time in secs},
@@ -409,7 +409,6 @@
 slightly worse then the matcher in Ruby and Python.
 Ooops\ldots
 
-\pgfplotsset{compat=1.11}
 \begin{center}
 \begin{tikzpicture}
\begin{axis}[
    xlabel={\pcode{a}s},
    ylabel={time in secs},
     enlargelimits=false,
@@ -461,7 +460,6 @@
 is. This means we have to also add cases for $nullable$ and
 $der$. Does the change have any effect?
 
-\pgfplotsset{compat=1.11}
 \begin{center}
 \begin{tikzpicture}
\begin{axis}[
    xlabel={\pcode{a}s},
    ylabel={time in secs},
     enlargelimits=false,
@@ -469,7 +467,7 @@
     xmax=1000,
    ytick={0,5,...,30},
     scaled ticks=false,
     axis lines=left,
-    width=10cm,
+    width=9.5cm,
     height=5cm, 
     legend entries={Python,Ruby,Scala V1,Scala V2},  
     legend pos=outer north east,
@@ -537,7 +535,6 @@
 \pcode{ders}-function.\label{scala2}}
 \end{figure}
 
-\pgfplotsset{compat=1.11}
 \begin{center}
 \begin{tikzpicture}
\begin{axis}[
    xlabel={\pcode{a}s},
    ylabel={time in secs},
     enlargelimits=false,
diff -r ee4304bc6350 -r 92e6985018ae progs/app01.scala
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/progs/app01.scala	Mon Sep 29 00:45:38 2014 +0100
@@ -0,0 +1,7 @@
+abstract class Rexp
+case object NULL extends Rexp
+case object EMPTY extends Rexp
+case class CHAR(c: Char) extends Rexp
+case class ALT(r1: Rexp, r2: Rexp) extends Rexp 
+case class SEQ(r1: Rexp, r2: Rexp) extends Rexp 
+case class STAR(r: Rexp) extends Rexp 
diff -r ee4304bc6350 -r 92e6985018ae slides/slides02.pdf
Binary file slides/slides02.pdf has changed
diff -r ee4304bc6350 -r 92e6985018ae slides/slides02.tex
--- a/slides/slides02.tex	Sun Sep 28 22:30:25 2014 +0100
+++ b/slides/slides02.tex	Mon Sep 29 00:45:38 2014 +0100
@@ -12,6 +12,8 @@
         numbers=none,
         xleftmargin=0mm}
 
+\pgfplotsset{compat=1.11}
+
 \newcommand{\bl}[1]{\textcolor{blue}{#1}}     
 
 % beamer stuff 
@@ -43,119 +45,154 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{\begin{tabular}{@ {}c@ {}}An Efficient Regular\\[-1mm] 
+    Expression Matcher\end{tabular}}
+
+\footnotesize
+\begin{center}
+\begin{tabular}{@{}cc@{}}
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={\pcode{a}s},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,5,...,30},
+    xmax=30,
+    ymax=35,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=4.5cm,
+    height=4.5cm, 
+    legend entries={Python,Ruby},  
+    legend pos=north west,
+    legend cell align=left  
+]
+\addplot[blue,mark=*, mark options={fill=white}] 
+  table {re-python.data};
+\addplot[brown,mark=pentagon*, mark options={fill=white}] 
+  table {re-ruby.data};  
+\end{axis}
+\end{tikzpicture}
+&
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={\pcode{a}s},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,3000,...,12000},
+    xmax=12000,
+    ymax=35,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=5.5cm,
+    height=4.5cm
+]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+\end{axis}
+\end{tikzpicture}
+\end{tabular}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
 \frametitle{Languages, Strings}
 
 \begin{itemize}
-\item A \alert{language} is a set of strings.\medskip
+\item \alert{\bf Strings} are lists of characters, for example
 \begin{center}
-\bl{\{[], hello, foobar, a, abc\}}
+\bl{$[]$},\;\bl{$abc$}  \hspace{2cm}(Pattern match: \bl{$c\!::\!s$})
+\end{center}\bigskip
+
+
+\item A \alert{\bf language} is a set of strings, for example\medskip
+\begin{center}
+\bl{$\{[], hello, \textit{foobar}, a, abc\}$}
 \end{center}\bigskip
 
-\item The \alert{meaning} of a regular expression is a set of 
-  strings, or language.
+\item \alert{\bf Concatenation} of strings and sets
+
+\begin{center}
+\begin{tabular}{rcl}
+\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\
+\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
+\end{tabular}
+\end{center}
+
+%\item The \alert{\bf meaning} of a regular expression is a set of 
+%  strings, or language.
 \end{itemize}  
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Strings\end{tabular}}
-
-Different ways of writing strings:
-
-\begin{center}
-\begin{tabular}{ccc}
-\bl{\consolas"$hello$"}\quad{} &  \bl{$[h, e, l, l, o]$} & \quad\bl{$h\!::\!e\!::\!l\!::\!l\!::\!o\!::\!N\!il$}\bigskip\\
-\bl{\consolas ""}       &       \bl{$[]$}                & \bl{$N$\!$il$}
-\end{tabular}
-\end{center}\pause
-
-The concatenation operation on strings and sets of strings:
-
-\begin{center}
-\begin{tabular}{l}
-\bl{{\consolas"$f\!oo$"}$\;@\;${\consolas"$bar$"}$\;=\;${\consolas"$f\!oobar$"}}\medskip\\
-\bl{$A \;@\; B \dn \{ s_1 @ s_2 \mid s_1 \in A \wedge s_2 \in B\}$}
-\end{tabular}
-\end{center}
-  
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
 
 Their inductive definition:
 
 
-\begin{textblock}{6}(2,6.5)
+\begin{textblock}{6}(2,7.5)
   \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
   \bl{$r$} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
-         & \bl{$\mid$} & \bl{$\epsilon$}        & empty string / {\consolas""} / $[]$\\
+         & \bl{$\mid$} & \bl{$\epsilon$}       & empty string / \pcode{""} / $[]$\\
          & \bl{$\mid$} & \bl{$c$}                         & character\\
          & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
          & \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\
-         & \bl{$\mid$} & \bl{$r^*$}                   & star (zero or more)\\
+         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\
   \end{tabular}
   \end{textblock}
   
   
-\only<2->{
-\begin{textblock}{9}(4,0.5)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
-{\normalsize\color{darkgray}
-\begin{minipage}{9cm}
-\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{../progs/app51.scala}}}}
-\end{minipage}};
-\end{tikzpicture}
+\only<2->{\footnotesize
+\begin{textblock}{9}(2,0.5)
+\begin{bubble}[9.8cm]
+\lstinputlisting{../progs/app01.scala}
+\end{bubble}
 \end{textblock}}
   
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}}
 
 \begin{textblock}{15}(1,4)
  \begin{tabular}{@ {}rcl}
  \bl{$L(\varnothing)$}     & \bl{$\dn$} & \bl{$\varnothing$}\\
- \bl{$L(\epsilon)$}          & \bl{$\dn$} & \bl{$\{$""$\}$}\\
- \bl{$L(c)$}                     & \bl{$\dn$} & \bl{$\{"c"\}$}\\
- \bl{$L(r_1 + r_2)$}        & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ \bl{$L(\epsilon)$}        & \bl{$\dn$} & \bl{$\{$[]$\}$}\\
+ \bl{$L(c)$}               & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ \bl{$L(r_1 + r_2)$}       & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
  \bl{$L(r_1 \cdot r_2)$}  & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
  \bl{$L(r^*)$}                   & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0} L(r)^n$}\\
   \end{tabular}\bigskip
   
 \only<2->{  
-\hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{""\}$}\\
+\hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{[]\}$}\\
 \textcolor{blue}{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}}  
 \end{textblock}
 
-
-
 \only<1->{
 \begin{textblock}{6}(9,12)\small
 \bl{$L$} is a function from regular expressions to sets of strings\\
 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
 \end{textblock}}
 
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 
 \large
@@ -163,92 +200,112 @@
 What is \bl{$L(a^*)$}?
 \end{center}  
   
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Concrete Equivalences\end{tabular}}
 
+\begin{center}
+\bl{\begin{tabular}{rcl}
+$(a + b)  + c$ & $\equiv$ & $a + (b + c)$\\
+$a + a$        & $\equiv$ & $a$\\
+$a + b$        & $\equiv$ & $b + a$\\
+$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\
+$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause
+$a \cdot a$       & $\not\equiv$ & $a$\\
+$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Corner Cases\end{tabular}}
+
+\begin{center}
+\bl{\begin{tabular}{rcl}
+$a \cdot \varnothing$ & $\not\equiv$ & $a$\\
+$a + \epsilon$ & $\not\equiv$ & $a$\\
+$\epsilon$ & $\equiv$ & $\varnothing^*$\\
+$\epsilon^*$ & $\equiv$ & $\epsilon$\\
+$\varnothing^*$ & $\not\equiv$ & $\varnothing$\\
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}Simplification Rules\end{tabular}}
+
+\begin{center}
+\bl{\begin{tabular}{rcl}
+$r + \varnothing$  & $\equiv$ & $r$\\
+$\varnothing + r$  & $\equiv$ & $r$\\
+$r \cdot \epsilon$ & $\equiv$ & $r$\\
+$\epsilon \cdot r$     & $\equiv$ & $r$\\
+$r \cdot \varnothing$ & $\equiv$ & $\varnothing$\\
+$\varnothing \cdot r$ & $\equiv$ & $\varnothing$\\
+$r + r$ & $\equiv$ & $r$
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 \newcommand{\YES}{\textcolor{gray}{yes}}
 \newcommand{\NO}{\textcolor{gray}{no}}
 \newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}}
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}}
+\frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}}
+
+\large
+A regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if
 
 \begin{center}
-\begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l}
-&\bl{$(a + b)  + c$} & \bl{$\equiv^?$} & \bl{$a + (b + c)$} & \onslide<2->{\YES}\\
-&\bl{$a + a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<3->{\YES}\\
-&\bl{$(a \cdot b)  \cdot c$} & \bl{$\equiv^?$} & \bl{$a \cdot (b \cdot c)$} & \onslide<4->{\YES}\\
-&\bl{$a \cdot a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<5->{\NO}\\
-&\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\
-&\bl{$\varnothing^*$} & \bl{$\equiv^?$} & \bl{$\varnothing$} & \onslide<7->{\NO}\\
-\FORALLR &\bl{$r \cdot \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<8->{\YES}\\
-\FORALLR &\bl{$r + \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<9->{\NO}\\
-\FORALLR &\bl{$r + \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<10->{\YES}\\
-\FORALLR &\bl{$r \cdot \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<11->{\NO}\\
-&\bl{$c \cdot (a + b)$} & \bl{$\equiv^?$} & \bl{$(c \cdot a) + (c \cdot b)$} & \onslide<12->{\YES}\\
-&\bl{$a^*$} & \bl{$\equiv^?$} & \bl{$\epsilon + (a \cdot a^*)$} & \onslide<13->{\YES}
-\end{tabular}
+\bl{$s \in L(r)$}\\ 
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}}
-
-\large
-a regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if
-
-\begin{center}
-\bl{$s \in L(r)$}\\ 
-\end{center}\bigskip\bigskip\pause
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
 
-\mbox{}\\[-13mm]
-
-\begin{tikzpicture}[y=.2cm, x=.3cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (30,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
-    	%ticks
-    	\foreach \x in {0,5,...,30}
-     		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\x};
-    	\foreach \y in {0,5,...,30}
-     		\draw (1pt,\y) -- (-3pt,\y) 
-     			node[anchor=east] {\y}; 
-	%labels      
-	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
-
-	%plots
-	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
-		file {re-python.data};
-	\draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
-		file {re-ruby.data};
-    
-	%legend
-	\begin{scope}[shift={(4,20)}] 
-	\draw[color=blue] (0,0) -- 
-		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
-		node[right]{\small Python};
-	\draw[yshift=-\baselineskip, color=brown] (0,0) -- 
-		plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Ruby};
-	\end{scope}
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={\pcode{a}s},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,5,...,30},
+    xmax=30,
+    ymax=35,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=9cm,
+    height=7cm, 
+    legend entries={Python,Ruby},  
+    legend pos=north west,
+    legend cell align=left  
+]
+\addplot[blue,mark=*, mark options={fill=white}] 
+  table {re-python.data};
+\addplot[brown,mark=pentagon*, mark options={fill=white}] 
+  table {re-ruby.data};  
+\end{axis}
 \end{tikzpicture}
+\end{center}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -278,7 +335,7 @@
 \begin{frame}[t]
 \frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}}
 
-\small
+
 \ldots{}whether a regular expression can match the empty string:
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
@@ -291,18 +348,6 @@
 \end{tabular}
 \end{center}
 
-\only<2->{
-\begin{textblock}{9}(3.4,10)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
-{\normalsize\color{darkgray}
-\begin{minipage}{9cm}
-\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{../progs/app5.scala}}}}
-\end{minipage}};
-\end{tikzpicture}
-\end{textblock}}
-  
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -313,7 +358,8 @@
 \frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}
 
 \large
-If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular expression that matches \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
+If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular 
+expression that matches \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
 
 \small
 \bl{$der\,c\,r$} gives the answer
@@ -334,25 +380,13 @@
   \bl{$der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\
   & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ 
   & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
-  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause
+  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\\pause
 
-  \bl{$der\!s\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
-  \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
+  \bl{$\textit{ders}\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
+  \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\
   \end{tabular}
 \end{center}
 
-\only<3->{
-\begin{textblock}{10.5}(2,5)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 
-{\normalsize\color{darkgray}
-\begin{minipage}{10.5cm}
-\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{../progs/app6.scala}}}}
-\end{minipage}};
-\end{tikzpicture}
-\end{textblock}}
-
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -365,8 +399,9 @@
 
 \begin{center}
 \begin{tabular}{l}
-\bl{$der\,a\,r$}\\
-\bl{$der\,b\,r$}
+\bl{$der\,a\,r =?$}\\
+\bl{$der\,b\,r =?$}\\
+\bl{$der\,c\,r =?$}
 \end{tabular}
 \end{center}
 
@@ -377,47 +412,189 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[t]
+\frametitle{The Algorithm}
+
+\begin{center}
+\begin{tabular}{@{}rll@{}}
+Input: & \bl{$r_1$}, \bl{$abc$}\medskip\\
+Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = der\,a\,r_1)$}\smallskip\\
+Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = der\,b\,r_2)$}\smallskip\\
+Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = der\,b\,r_3)$}\smallskip\\
+Step 4: & the string is exhausted; test & (\bl{$nullable(r_4)$})\\
+        & whether \bl{$r_4$} can recognise\\
+        & the empty string\smallskip\\
+Output: & result of the test\\
+        & $\Rightarrow true \,\text{or}\, \textit{false}$\\        
+\end{tabular}
+\end{center}
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
 
-\mbox{}\\[-13mm]
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={\pcode{a}s},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,5,...,30},
+    xmax=30,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=7cm,
+    height=7cm, 
+    legend entries={Python,Ruby,Scala V1},  
+    legend pos=outer north east,
+    legend cell align=left  
+]
+\addplot[blue,mark=*, mark options={fill=white}] 
+  table {re-python.data};
+\addplot[brown,mark=pentagon*, mark options={fill=white}] 
+  table {re-ruby.data};  
+\addplot[red,mark=triangle*,mark options={fill=white}] 
+  table {re1.data};  
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}A Problem\end{tabular}}
+
+We represented the ``n-times'' \bl{$a\{n\}$} as a sequence regular expression:
 
-\begin{tikzpicture}[y=.2cm, x=.3cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (30,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
-    	%ticks
-    	\foreach \x in {0,5,...,30}
-     		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\x};
-    	\foreach \y in {0,5,...,30}
-     		\draw (1pt,\y) -- (-3pt,\y) 
-     			node[anchor=east] {\y}; 
-	%labels      
-	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
+\begin{center}
+\begin{tabular}{rl}
+1: & \bl{$a$}\\
+2: & \bl{$a\cdot a$}\\
+3: & \bl{$a\cdot a\cdot a$}\\
+& \ldots\\
+13: & \bl{$a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a$}\\
+& \ldots\\
+20:
+\end{tabular}
+\end{center}
+
+This problem is aggravated with \bl{$a?$} being represented as \bl{$\epsilon + a$}.
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Solving the Problem\end{tabular}}
+
+What happens if we extend our regular expressions
+
+\begin{center}
+\begin{tabular}{rcl}
+\bl{$r$} & \bl{$::=$} & \bl{\ldots}\\
+             & \bl{$\mid$} & \bl{$r\{n\}$}\\
+             & \bl{$\mid$} & \bl{$r?$} 
+\end{tabular}
+\end{center}
+
+What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}?
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
 
-	%plots
-	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
-		file {re-python.data};
-	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
-		file {re1.data};
-         \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
-		file {re-ruby.data};
-		
-    
-	%legend
-	\begin{scope}[shift={(4,20)}] 
-	\draw[color=blue] (0,0) -- 
-		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
-		node[right]{\small Python};
-	\draw[yshift=-\baselineskip, color=brown] (0,0) -- 
-		plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Ruby};
-        \draw[yshift=\baselineskip, color=red] (0,0) -- 
-		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Scala V1};	
-	\end{scope}
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={\pcode{a}s},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,200,...,1000},
+    xmax=1000,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=9.5cm,
+    height=7cm, 
+    legend entries={Python,Ruby,Scala V1,Scala V2},  
+    legend pos=north west,
+    legend cell align=left  
+]
+\addplot[blue,mark=*, mark options={fill=white}] 
+  table {re-python.data};
+\addplot[brown,mark=pentagon*, mark options={fill=white}] 
+  table {re-ruby.data};  
+\addplot[red,mark=triangle*,mark options={fill=white}] 
+  table {re1.data};  
+\addplot[green,mark=square*,mark options={fill=white}] 
+  table {re2b.data};
+\end{axis}
 \end{tikzpicture}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Examples\end{tabular}}
+
+Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\
+\bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$}\\
+\bl{$der\,c\,r = ((\varnothing \cdot b) + \varnothing)\cdot r$}
+\end{tabular}
+\end{center}
+
+What are these regular expressions equivalent to?
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
+
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={\pcode{a}s},
+    ylabel={time in secs},
+    enlargelimits=false,
+    xtick={0,3000,...,12000},
+    xmax=12000,
+    ymax=35,
+    ytick={0,5,...,30},
+    scaled ticks=false,
+    axis lines=left,
+    width=9cm,
+    height=7cm
+]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+\end{axis}
+\end{tikzpicture}
+\end{center}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -471,7 +648,7 @@
 Assume \bl{$P(r)$} is the property:
 
 \begin{center}
-\bl{$nullable(r)$} if and only if \bl{$"" \in L(r)$}
+\bl{$nullable(r)$} if and only if \bl{$[] \in L(r)$}
 \end{center}
 
 \end{frame}}
@@ -482,6 +659,35 @@
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Proofs about Rexp (4)\end{tabular}}
 
+
+\begin{center}
+\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$rev(\varnothing)$   & $\dn$ & $\varnothing$\\
+$rev(\epsilon)$         & $\dn$ & $\epsilon$\\
+$rev(c)$                      & $\dn$ & $c$\\
+$rev(r_1 + r_2)$        & $\dn$ & $rev(r_1) + rev(r_2)$\\
+$rev(r_1 \cdot r_2)$  & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
+$rev(r^*)$                   & $\dn$ & $rev(r)^*$\\
+\end{tabular}}
+\end{center}
+
+
+We can prove
+
+\begin{center}
+\bl{$L(rev(r)) = \{s^{-1} \;|\; s \in L(r)\}$}
+\end{center}
+
+by induction on \bl{$r$}.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Rexp (5)\end{tabular}}
+
 Let \bl{$Der\,c\,A$} be the set defined as
 
 \begin{center}
@@ -523,281 +729,13 @@
 We can finally prove
 
 \begin{center}
-\bl{$matcher(r, s)$}  if and only if  \bl{$s \in L(r)$} 
+\bl{$matches(r, s)$}  if and only if  \bl{$s \in L(r)$} 
 \end{center}
 
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-13mm]
-
-\begin{tikzpicture}[y=.2cm, x=.3cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (30,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
-    	%ticks
-    	\foreach \x in {0,5,...,30}
-     		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\x};
-    	\foreach \y in {0,5,...,30}
-     		\draw (1pt,\y) -- (-3pt,\y) 
-     			node[anchor=east] {\y}; 
-	%labels      
-	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
-
-	%plots
-	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
-		file {re-python.data};
-	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
-		file {re1.data};
-         \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
-		file {re-ruby.data};
-		
-    
-	%legend
-	\begin{scope}[shift={(4,20)}] 
-	\draw[color=blue] (0,0) -- 
-		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
-		node[right]{\small Python};
-	\draw[yshift=-\baselineskip, color=brown] (0,0) -- 
-		plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Ruby};
-        \draw[yshift=\baselineskip, color=red] (0,0) -- 
-		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Scala V1};	
-	\end{scope}
-\end{tikzpicture}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}A Problem\end{tabular}}
-
-We represented the ``n-times'' \bl{$a\{n\}$} as a sequence regular expression:
-
-\begin{center}
-\begin{tabular}{rl}
-1: & \bl{$a$}\\
-2: & \bl{$a\cdot a$}\\
-3: & \bl{$a\cdot a\cdot a$}\\
-& \ldots\\
-13: & \bl{$a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a$}\\
-& \ldots\\
-20:
-\end{tabular}
-\end{center}
-
-This problem is aggravated with \bl{$a?$} being represented as \bl{$\epsilon + a$}.
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Solving the Problem\end{tabular}}
-
-What happens if we extend our regular expressions
-
-\begin{center}
-\begin{tabular}{rcl}
-\bl{$r$} & \bl{$::=$} & \bl{\ldots}\\
-             & \bl{$\mid$} & \bl{$r\{n\}$}\\
-             & \bl{$\mid$} & \bl{$r?$} 
-\end{tabular}
-\end{center}
-
-What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}?
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-13mm]
-
-\begin{tikzpicture}[y=.2cm, x=.12cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (70,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
-    	%ticks
-    	\foreach \x in {0,10,...,70}
-     		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\x};
-    	\foreach \y in {0,5,...,30}
-     		\draw (1pt,\y) -- (-3pt,\y) 
-     			node[anchor=east] {\y}; 
-	%labels      
-	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
-
-	%plots
-	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
-		file {re-python.data};
-	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
-		file {re1.data};
-         \draw[color=green] plot[mark=square*, mark options={fill=white} ] 
-		file {re2a.data};
-         \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
-		file {re-ruby.data};
-    
-	%legend
-	\begin{scope}[shift={(4,20)}] 
-	\draw[color=blue] (0,0) -- 
-		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 
-		node[right]{\small Python};
-	\draw[yshift=-\baselineskip, color=brown] (0,0) -- 
-		plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Ruby};
-	\draw[yshift=\baselineskip, color=red] (0,0) -- 
-		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Scala V1};	
-	\draw[yshift=2\baselineskip, color=green] (0,0) -- 
-		plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0)
-		node[right]{\small Scala V2};	
-	\end{scope}
-\end{tikzpicture}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-13mm]
-
-\begin{tabular}{@ {\hspace{-5mm}}l}
-\begin{tikzpicture}[y=.2cm, x=.01cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (1000,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
-    	%ticks
-    	\foreach \x in {0,100,...,1000}
-     		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\x};
-    	\foreach \y in {0,5,...,30}
-     		\draw (1pt,\y) -- (-3pt,\y) 
-     			node[anchor=east] {\y}; 
-	%labels      
-	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
-
-	%plots
-	\draw[color=blue] plot[mark=*, mark options={fill=white}] 
-		file {re-python.data};
-	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
-		file {re1.data};
-         \draw[color=green] plot[mark=square*, mark options={fill=white} ] 
-		file {re2b.data};
-         \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
-		file {re-ruby.data};
-    
-	%legend
-	\begin{scope}[shift={(100,20)}] 
-	\draw[color=blue] (0,0) -- 
-		plot[mark=*, mark options={fill=white}] (0.25,0) -- (50,0) 
-		node[right]{\small Python};
-	\draw[yshift=-13, color=brown] (0,0) -- 
-		plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (50,0)
-		node[right]{\small Ruby};
-	\draw[yshift=13, color=red] (0,0) -- 
-		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0)
-		node[right]{\small Scala V1};	
-	\draw[yshift=26, color=green] (0,0) -- 
-		plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0)
-		node[right]{\small Scala V2};	
-	\end{scope}
-\end{tikzpicture}
-\end{tabular}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Examples\end{tabular}}
-
-Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with
-
-\begin{center}
-\begin{tabular}{l}
-\bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\
-\bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$}
-\end{tabular}
-\end{center}
-
-What are these regular expressions equal to?
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-9mm]
-
-\begin{tabular}{@ {\hspace{-5mm}}l}
-\begin{tikzpicture}[y=.2cm, x=.0008cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (12000,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
-    	%ticks
-    	\foreach \x in {0,2000,...,12000}
-     		\draw (\x,1pt) -- (\x,-3pt)
-			node[anchor=north] {\x};
-    	\foreach \y in {0,5,...,30}
-     		\draw (1pt,\y) -- (-3pt,\y) 
-     			node[anchor=east] {\y}; 
-	%labels      
-	\node[below=0.6cm] at (x axis mid) {\bl{a}s};
-	\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
-
-	%plots
-	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 
-		file {re1.data};
-         \draw[color=green] plot[mark=square*, mark options={fill=white} ] 
-		file {re2b.data};
-	\draw[color=black] plot[mark=square*, mark options={fill=white} ] 
-		file {re3.data};	 
-    
-	%legend
-	\begin{scope}[shift={(2000,20)}] 
-	\draw[color=red] (0,0) -- 
-		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0) 
-		node[right]{\small Scala V1};
-	\draw[yshift=13, color=green] (0,0) -- 
-		plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0)
-		node[right]{\small Scala V2};	
-	\draw[yshift=26, color=black] (0,0) -- 
-		plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0)
-		node[right]{\small Scala V3};	
-	\end{scope}
-\end{tikzpicture}
-\end{tabular}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
 \end{document}
 
 %%% Local Variables: