# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1348645764 -3600
# Node ID f3d92595abe794dd2210487e73cc08b19fb486b4
# Parent  27c0abdb39d573e34e42892b875bc1e76f3b6402
tuned

diff -r 27c0abdb39d5 -r f3d92595abe7 slides01.pdf
Binary file slides01.pdf has changed
diff -r 27c0abdb39d5 -r f3d92595abe7 slides01.tex
--- a/slides01.tex	Wed Sep 26 08:26:02 2012 +0100
+++ b/slides01.tex	Wed Sep 26 08:49:24 2012 +0100
@@ -365,7 +365,7 @@
 \begin{textblock}{6}(2,4)
   \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
   \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\
-         & \bl{$\mid$} & \bl{$\epsilon$}        & empty string / ""\\
+         & \bl{$\mid$} & \bl{$\epsilon$}        & empty string / "" / []\\
          & \bl{$\mid$} & \bl{c}                         & character\\
          & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$} & sequence\\
          & \bl{$\mid$} & \bl{r$_1$ + r$_2$}  & alternative / choice\\
@@ -402,20 +402,117 @@
  \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{$\{$ s$_1$ @ s$_2$ $|$ s$_1$ $\in$ $L$(r$_1$) $\wedge$ s$_2$ $\in$ 
      $L$(r$_2$) $\}$}\\
- \bl{$L$(r$^*$)}                   & \bl{$\dn$} & \onslide<3>{\bl{$\bigcup_{n \ge 0}$ $L$(r)$^n$}}\\
+ \bl{$L$(r$^*$)}                   & \bl{$\dn$} & \onslide<4->{\bl{$\bigcup_{n \ge 0}$ $L$(r)$^n$}}\\
   \end{tabular}\bigskip
   
 \onslide<2->{
 \hspace{5mm}\bl{$L$(r)$^0$ $\;\dn\;$ $\{$""$\}$}\\
-\bl{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$}\hspace{9mm}\small\textcolor{gray}{(append on sets)}\\
-\small\hspace{5cm}\textcolor{gray}{$\{$ s$_1$ @ s$_2$ $|$ s$_1$ $\in$ $L$(r$_1$) $\wedge$ s$_2$ $\in$ 
-     $L$(r$_2$) $\}$}
+\bl{$L$(r)$^{n+1}$ $\;\dn\;$ $L$(r) @ $L$(r)$^n$}\hspace{9mm}\onslide<3->{\small\textcolor{gray}{(append on sets)}\\
+\small\hspace{5cm}\textcolor{gray}{$\{$ s$_1$ @ s$_2$ $|$ s$_1$ $\in$ $L$(r) $\wedge$ s$_2$ $\in$ 
+     $L$(r)$^n$ $\}$}}
 }  
     \end{textblock}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Meaning of a Matching\end{tabular}}
+
+\large
+a regular expression \bl{r} matches a string \bl{s} is defined as
+
+\begin{center}
+\bl{s $\in$ $L$(r)}\\ 
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Nullability\end{tabular}}
+
+\small
+whether a regular expression matches the empty string:\medskip
+
+
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{app5.scala}}}
+
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}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
+
+\small
+\bl{der c r} gives the answer
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Derivative\end{tabular}}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
+  \bl{der c ($\varnothing$)}            & \bl{$\dn$} & \bl{$\varnothing$} & \\
+  \bl{der c ($\epsilon$)}           & \bl{$\dn$} & \bl{$\varnothing$} & \\
+  \bl{der c (d)}           & \bl{$\dn$} & \bl{if c $=$ d then [] else $\varnothing$} & \\
+  \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\
+  \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{((der c r$_1$) $\cdot$ r$_2$) + } & \\
+       &          & \bl{\hspace{3mm}(if nullable r$_1$ then der c r$_2$ else $\varnothing$)}\\
+  \bl{der c (r$^*$)}          & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)} &\smallskip\\\pause
+
+  \bl{ders [] r}     & \bl{$\dn$} & \bl{r} & \\
+  \bl{ders (c::s) r} & \bl{$\dn$} & \bl{ders s (der c r)} & \\
+  \end{tabular}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Derivative\end{tabular}}
+
+
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{app6.scala}}}
+
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}The Matcher\end{tabular}}
+
+
+{\lstset{language=Scala}\fontsize{8}{10}\selectfont
+\texttt{\lstinputlisting{app7.scala}}}
+
+
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
 \begin{frame}[c]