# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1380668376 -3600
# Node ID a6684e8961d0c4f8f823132cf29532466b8df24c
# Parent  6a5b59690f7d1d0f1a0be8f2653b491517c0e23d
added

diff -r 6a5b59690f7d -r a6684e8961d0 progs/re1.scala
--- a/progs/re1.scala	Mon Sep 30 20:03:41 2013 +0100
+++ b/progs/re1.scala	Tue Oct 01 23:59:36 2013 +0100
@@ -52,7 +52,7 @@
 
 //example
 //val r = STAR(ALT(SEQ(CHAR('a'), CHAR('b')), CHAR('b')))
-//der('b', r)
+//der('a', r)
 //der('b', r)
 
 //one or zero
@@ -65,7 +65,7 @@
   case n => SEQ(r, NTIMES(r, n - 1))
 }
 
-def RTEST(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n))
+def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n))
 
 def time_needed[T](i: Int, code: => T) = {
   val start = System.nanoTime()
@@ -75,7 +75,7 @@
 }
 
 for (i <- 1 to 29) {
-  println(i + ": " + "%.5f".format(time_needed(1, matcher(RTEST(i), "a" * i))))
+  println(i + ": " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i))))
 }
 
 
diff -r 6a5b59690f7d -r a6684e8961d0 progs/re3.scala
--- a/progs/re3.scala	Mon Sep 30 20:03:41 2013 +0100
+++ b/progs/re3.scala	Tue Oct 01 23:59:36 2013 +0100
@@ -85,11 +85,10 @@
 def matcher(r: Rexp, s: String) : Boolean = nullable(ders(s.toList, r))
 
 
-
 //one or zero
 def OPT(r: Rexp) = ALT(r, EMPTY)
 
-def RTEST(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n))
+def EVIL(n: Int) = SEQ(NTIMES(OPT("a"), n), NTIMES("a", n))
 
 def time_needed[T](i: Int, code: => T) = {
   val start = System.nanoTime()
@@ -100,7 +99,7 @@
 
 
 for (i <- 1 to 11001 by 500) {
-  println(i + " " + + " " + time_needed(1, matcher(RTEST(i), "a" * i)))
+  println(i + " " + "%.5f".format(time_needed(1, matcher(EVIL(i), "a" * i))))
 }
 
 
diff -r 6a5b59690f7d -r a6684e8961d0 slides/slides02.pdf
Binary file slides/slides02.pdf has changed
diff -r 6a5b59690f7d -r a6684e8961d0 slides/slides02.tex
--- a/slides/slides02.tex	Mon Sep 30 20:03:41 2013 +0100
+++ b/slides/slides02.tex	Tue Oct 01 23:59:36 2013 +0100
@@ -134,6 +134,70 @@
 28 34.79653
 \end{filecontents}
 
+\begin{filecontents}{re1.data}
+1 0.00179
+2 0.00011
+3 0.00014
+4 0.00026
+5 0.00050
+6 0.00095
+7 0.00190
+8 0.00287
+9 0.00779
+10 0.01399
+11 0.01894
+12 0.03666
+13 0.07994
+14 0.08944
+15 0.02377
+16 0.07392
+17 0.22798
+18 0.65310
+19 2.11360
+20 6.31606
+21 21.46013
+\end{filecontents}
+
+\begin{filecontents}{re2a.data}
+1 0.00227
+5 0.00027
+10 0.00075
+15 0.00178
+20 0.00102
+25 0.00028
+30 0.00040
+35 0.00052
+40 0.00075
+45 0.00125
+50 0.00112
+55 0.00099
+60 0.00113
+65 0.00137
+70 0.00170
+\end{filecontents}
+
+\begin{filecontents}{re2b.data}
+1 0.00020
+51 0.00080
+101 0.00678
+151 0.01792
+201 0.04815
+251 0.09648
+301 0.23195
+351 0.52646
+401 0.96277
+451 1.57726
+501 2.00166
+551 2.98341
+601 4.81181
+651 6.57054
+701 9.73973
+751 14.25762
+801 14.80760
+851 19.60958
+901 25.43550
+951 31.96038
+\end{filecontents}
 
 \begin{document}
 
@@ -216,12 +280,12 @@
 
 \begin{textblock}{6}(2,6.5)
   \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
-  \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
+  \bl{$r$} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
          & \bl{$\mid$} & \bl{$\epsilon$}        & empty string / {\consolas""} / $[]$\\
-         & \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{$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)\\
   \end{tabular}
   \end{textblock}
   
@@ -319,13 +383,13 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Specification\\[-1mm] of Matching\end{tabular}}
+\frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}}
 
 \large
-a regular expression \bl{r} matches a string \bl{s} is defined as
+a regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if
 
 \begin{center}
-\bl{s $\in$ $L$(r)}\\ 
+\bl{$s \in L(r)$}\\ 
 \end{center}\bigskip\bigskip\pause
 
 \end{frame}}
@@ -356,11 +420,7 @@
 	%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 {re2.data};
-         \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
+	\draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] 
 		file {re-ruby.data};
     
 	%legend
@@ -437,7 +497,7 @@
 \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
@@ -460,8 +520,8 @@
   & & \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\!s\, [] r$}     & \bl{$\dn$} & \bl{$r$} & \\
-  \bl{$der\!s\, (c\!::\!s) r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
+  \bl{$der\!s\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
+  \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
   \end{tabular}
 \end{center}
 
@@ -483,12 +543,16 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}}
+\frametitle{\begin{tabular}{c}Examples\end{tabular}}
 
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
 
-{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{../progs/app7.scala}}}
-
+\begin{center}
+\begin{tabular}{l}
+\bl{$der\,a\,r$}\\
+\bl{$der\,b\,r$}
+\end{tabular}
+\end{center}
 
 
 \end{frame}}
@@ -497,22 +561,70 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[t]
-\frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}}
+\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}[t]
+\frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}}
 
 Remember their inductive definition:\\[5cm]
 
 \begin{textblock}{6}(5,5)
   \begin{tabular}{@ {}rrl}
-  \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}\\
+  \bl{$r$} & \bl{$::=$}  & \bl{$\varnothing$}\\
          & \bl{$\mid$} & \bl{$\epsilon$}       \\
-         & \bl{$\mid$} & \bl{c}                        \\
-         & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$}\\
-         & \bl{$\mid$} & \bl{r$_1$ + r$_2$}  \\
-         & \bl{$\mid$} & \bl{r$^*$}                  \\
+         & \bl{$\mid$} & \bl{$c$}                        \\
+         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\
+         & \bl{$\mid$} & \bl{$r_1 + r_2$}  \\
+         & \bl{$\mid$} & \bl{$r^*$}                  \\
   \end{tabular}
   \end{textblock}
 
-If we want to prove something, say a property \bl{$P$(r)}, for all regular expressions \bl{r} then \ldots
+If we want to prove something, say a property \bl{$P(r)$}, for all regular expressions \bl{$r$} then \ldots
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -524,12 +636,12 @@
 
 \begin{itemize}
 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip
-\item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already
-holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip
-\item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already
-holds for \bl{r$_1$} and \bl{r$_2$}.
-\item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already
-holds for \bl{r}.
+\item \bl{$P$} holds for \bl{$r_1 + r_2$} under the assumption that \bl{$P$} already
+holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
+\item \bl{$P$} holds for \bl{$r_1 \cdot r_2$} under the assumption that \bl{$P$} already
+holds for \bl{$r_1$} and \bl{$r_2$}.\bigskip
+\item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
+holds for \bl{$r$}.
 \end{itemize}
 
 \end{frame}}
@@ -543,7 +655,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}}
@@ -552,14 +664,37 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Rexp (4)\end{tabular}}
+
+Let \bl{$Der\,c\,A$} be the set defined as
+
+\begin{center}
+\bl{$Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 
+\end{center}
+
+We can prove
+
+\begin{center}
+\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
+\end{center}
+
+by induction on \bl{$r$}.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
 \frametitle{\begin{tabular}{c}Proofs about Strings\end{tabular}}
 
-If we want to prove something, say a property \bl{$P$(s)}, for all strings \bl{s} then \ldots\bigskip
+If we want to prove something, say a property \bl{$P(s)$}, for all strings \bl{$s$} then \ldots\bigskip
 
 \begin{itemize}
 \item \bl{$P$} holds for the empty string, and\medskip
-\item \bl{$P$} holds for the string \bl{c::s} under the assumption that \bl{$P$}
-already holds for \bl{s}
+\item \bl{$P$} holds for the string \bl{$c\!::\!s$} under the assumption that \bl{$P$}
+already holds for \bl{$s$}
 \end{itemize}
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -569,16 +704,10 @@
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}}
 
-Let \bl{Der c A} be the set defined as
+We can finally prove
 
 \begin{center}
-\bl{Der c A $\dn$ $\{$ s $|$  c::s $\in$ A$\}$ } 
-\end{center}
-
-Assume that \bl{$L$(der c r) = Der c ($L$(r))}. Prove that
-
-\begin{center}
-\bl{matcher(r, s)  if and only if  s $\in$ $L$(r)} 
+\bl{$matcher(r, s)$}  if and only if  \bl{$s \in L(r)$} 
 \end{center}
 
 
@@ -587,6 +716,179 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \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}Problem\end{tabular}}
+
+We represented ``n-times'' as a sequence regular expression:
+
+\begin{center}
+\begin{tabular}{ll}
+1:
+\end{tabular}
+\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=.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}Regular Languages\end{tabular}}
 
@@ -618,6 +920,22 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}}
+
+
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{../progs/app7.scala}}}
+
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
 \end{document}
 
 %%% Local Variables: