diff -r ccfce105e36b -r 1e1b0fe66107 slides/slides04.tex
--- a/slides/slides04.tex	Fri Oct 09 14:48:06 2015 +0100
+++ b/slides/slides04.tex	Fri Oct 16 08:42:21 2015 +0100
@@ -49,7 +49,9 @@
 \path[->,red, line width=2mm] (nfa) edge node [above=4mm, black] 
      {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
 \path[->, red, line width=2mm] (dfa) edge node [below=5mm, black] {minimisation} (mdfa);
-\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);
+%%\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);
+\path[->, red, line width=2mm] (dfa) edge [bend left=45] node [below, black] {\begin{tabular}{l}Brzozowski's\\ method\end{tabular}} (rexp);
+
 \end{tikzpicture}\\
 \end{center}
 
@@ -58,9 +60,8 @@
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
-\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}}
+\frametitle{\bl{$a^?^{\{n\}} \cdot a^{\{n\}}$}}
 
 \begin{tikzpicture}
 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs},
@@ -85,10 +86,9 @@
 \end{axis}
 \end{tikzpicture}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{DFA to Rexp}
@@ -118,18 +118,16 @@
 \end{tabular}
 \end{center}
 
-\onslide<2->{
 Arden's Lemma:
 \begin{center}
 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
 \end{center}
-}
+
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{DFA Minimisation}
 
@@ -145,65 +143,6 @@
 \item All unmarked pairs can be merged.
 \end{enumerate}
 
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-\begin{center}
-\begin{tikzpicture}[>=stealth',very thick,auto,
-                             every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},]
-\node[state,initial]  (q_0)  {$q_0$};
-\node[state] (q_1) [right=of q_0] {$q_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop right] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);
-\end{tikzpicture}
-\end{center}
-
-\mbox{}\\[-20mm]\mbox{}
-
-\begin{center}
-\begin{tikzpicture}[scale=0.8,line width=0.8mm]
-\draw (0,0) -- (4,0);
-\draw (0,1) -- (4,1);
-\draw (0,2) -- (3,2);
-\draw (0,3) -- (2,3);
-\draw (0,4) -- (1,4);
-
-\draw (0,0) -- (0, 4);
-\draw (1,0) -- (1, 4);
-\draw (2,0) -- (2, 3);
-\draw (3,0) -- (3, 2);
-\draw (4,0) -- (4, 1);
-
-\draw (0.5,-0.5) node {$q_0$}; 
-\draw (1.5,-0.5) node {$q_1$}; 
-\draw (2.5,-0.5) node {$q_2$}; 
-\draw (3.5,-0.5) node {$q_3$};
- 
-\draw (-0.5, 3.5) node {$q_1$}; 
-\draw (-0.5, 2.5) node {$q_2$}; 
-\draw (-0.5, 1.5) node {$q_3$}; 
-\draw (-0.5, 0.5) node {$q_4$}; 
-
-\draw (0.5,0.5) node {\large$\star$}; 
-\draw (1.5,0.5) node {\large$\star$}; 
-\draw (2.5,0.5) node {\large$\star$}; 
-\draw (3.5,0.5) node {\large$\star$};
-\end{tikzpicture}
-\end{center}
-
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -288,56 +227,6 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Alternatives}
-\mbox{}\\[-17mm]\mbox{}
-
-\begin{center}
-\begin{tikzpicture}[>=stealth',very thick,auto,
-                    every state/.style={minimum size=0pt,
-                    inner sep=2pt,draw=blue!50,very thick,fill=blue!20}]
-\only<1>{\node[state,initial]  (q_0)  {$q_0$};}
-\only<2->{\node[state,accepting]  (q_0)  {$q_0$};}
-\node[state] (q_1) [right=of q_0] {$q_1$};
-\node[state] (q_2) [below right=of q_0] {$q_2$};
-\node[state] (q_3) [right=of q_2] {$q_3$};
-\only<1>{\node[state, accepting] (q_4) [right=of q_1] {$q_4$};}
-\only<2->{\node[state, initial right] (q_4) [right=of q_1] {$q_4$};}
-\only<1-2>{
-\path[->] (q_0) edge node [above]  {\alert{$a$}} (q_1);
-\path[->] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\path[->] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[->] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[->] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[->] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[->] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[->] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);}
-\only<3->{
-\path[<-] (q_0) edge node [above]  {\alert{$a$}} (q_1);
-\path[<-] (q_1) edge node [above]  {\alert{$a$}} (q_4);
-\path[<-] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\path[<-] (q_3) edge node [right]  {\alert{$a$}} (q_4);
-\path[<-] (q_2) edge node [above]  {\alert{$a$}} (q_3);
-\path[<-] (q_1) edge node [right]  {\alert{$b$}} (q_2);
-\path[<-] (q_0) edge node [above]  {\alert{$b$}} (q_2);
-\path[<-] (q_2) edge [loop left] node  {\alert{$b$}} ();
-\path[<-] (q_3) edge [bend left=95, looseness=1.3] node [below]  {\alert{$b$}} (q_0);}
-\end{tikzpicture}
-\end{center}
-\mbox{}\\[-18mm]
-
-\begin{itemize}
-\item<2-> exchange initial / accepting states
-\item<3-> reverse all edges
-\item<4-> subset construction $\Rightarrow$ DFA
-\item<5-> repeat once more \onslide<6->{$\Rightarrow$ minimal DFA}
-\end{itemize}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
 \frametitle{Regular Languages}
 
 Two equivalent definitions:\bigskip
@@ -382,13 +271,77 @@
 \end{tikzpicture}
 \end{center}\bigskip\bigskip
 
-\onslide<2>{But requires that the automaton is \alert{completed}!}
+But requires that the automaton is \alert{completed}!
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
+\frametitle{The Goal of this Course}
+\mbox{}\\[-26mm]\mbox{}
+
+\begin{center}
+  \begin{tikzpicture}[scale=1,
+                      node/.style={
+                      rectangle,rounded corners=3mm,
+                      very thick,draw=black!50,
+                      minimum height=18mm, minimum width=20mm,
+                      top color=white,bottom color=black!20}]
+
+  \node at (3.05, 1.8) {\Large\bf Write A Compiler};
+
+  \node (0) at (-2.3,0) {}; 
+  
+  \node (A) at (0,0)  [node] {};
+  \node [below right] at (A.north west) {lexer};
+
+  \node (B) at (3,0)  [node] {};
+  \node [below right=1mm] at (B.north west) 
+    {\mbox{}\hspace{-1mm}parser};
+
+  \node (C) at (6,0)  [node] {};
+  \node [below right] at (C.north west) 
+    {\mbox{}\hspace{-1mm}code gen};
+
+  \node (1) at (8.4,0) {}; 
+
+  \draw [->,line width=4mm] (0) -- (A); 
+  \draw [->,line width=4mm] (A) -- (B); 
+  \draw [->,line width=4mm] (B) -- (C); 
+  \draw [->,line width=4mm] (C) -- (1); 
+  \end{tikzpicture}
+  \end{center}
+  
+Today a lexer.  
+  
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Survey: Thanks!}
+\small
+
+\begin{itemize}
+\item {\bf My Voice} ``lecturer speaks in a low voice and 
+  is hard to hear him'' ``please use mic'' ``please use mic 
+  \& lecture recording''
+\item {\bf Pace} ``faster pace'' ``a bit quick for me 
+personally''
+\item {\bf Recording} ``please use recording class''
+\item {\bf Module Name} ``misleading''
+\item {\bf Examples} ``more examples''
+\item {\bf Assessment} ``really appreciate extension of 
+  first coursework'' 
+\end{itemize}
+  
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Lexing}
 
 \mbox{\lstinputlisting[language=While]{../progs/fib.while}}
 
@@ -405,29 +358,6 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{A Compiler}
-
-\begin{tikzpicture}[scale=1]
-  \draw[line width=1mm] (-0.3, 0) rectangle (1.5,2);
-  \draw[line width=1mm] (-1.8, 0) rectangle (-3.6,2);
-  \draw (4.4,1) node {Code Gen};
-  \draw (0.6,1.7) node {\small Parser};
-  \draw (-2.7,1.7) node {\small Lexer};
-  
-  \draw[red,->,line width = 2mm] (1.7,1) -- (3.2,1);
-  \draw[red,<-,line width = 2mm] (-0.6,1) -- (-1.6,1);
-  \draw[red,<-,line width = 2mm] (-3.8,1) -- (-4.8,1);
-
-  \draw (-4.6,1.7) node {\small string};
-  \draw (-1.1,1.7) node {\small tokens};
-  \draw ( 2.3,1.7) node {\small AST};
-\end{tikzpicture}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 
 \tt
@@ -518,6 +448,19 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
+\begin{frame}[c]
+
+The same problem with\medskip
+
+\[
+\bl{(ab + a) \cdot (c + bc)}
+\]\bigskip
+
+and the string $\bl{abc}$
+
+\end{frame}
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{POSIX: Two Rules}
@@ -616,6 +559,17 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+\begin{frame}[c]
+\small
+
+{\small\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app01.scala}}
+
+{\small\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app02.scala}}
+
+\end{frame}
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Mkeps}
@@ -659,6 +613,153 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{textblock}{10}(3,5)
+\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
+\node (r1)  {\bl{$r_1$}};
+\node (r2) [right=of r1] {\bl{$r_2$}};
+\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+\node (r3) [right=of r2] {\bl{$r_3$}};
+\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+\node (r4) [right=of r3] {\bl{$r_4$}};
+\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+\node (v4) [below=of r4] {\bl{$v_4$}};
+\draw[->,line width=1mm]  (r4) -- (v4);
+\node (v3) [left=of v4] {\bl{$v_3$}};
+\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+\node (v2) [left=of v3] {\bl{$v_2$}};
+\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+\node (v1) [left=of v2] {\bl{$v_1$}};
+\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+\draw[->,line width=0.5mm]  (r3) -- (v3);
+\draw[->,line width=0.5mm]  (r2) -- (v2);
+\draw[->,line width=0.5mm]  (r1) -- (v1);
+\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+\end{tikzpicture}
+\end{textblock}
+
+\only<2->{
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6cm]
+\small
+\begin{tabular}{ll}
+\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
+\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<2->{
+\begin{textblock}{6}(5,11.4)
+\begin{bubble}[7.6cm]
+\small
+\begin{tabular}{ll}
+\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
+\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
+\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
+\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Flatten}
+
+Obtaining the string underlying a value:
+
+\begin{center}
+\begin{tabular}{lcl}
+  \bl{$|Empty|$}     & \bl{$\dn$} & \bl{$[]$}\\
+  \bl{$|Char(c)|$}   & \bl{$\dn$} & \bl{$[c]$}\\
+  \bl{$|Left(v)|$}   & \bl{$\dn$} & \bl{$|v|$}\\
+  \bl{$|Right(v)|$}  & \bl{$\dn$} & \bl{$|v|$}\\
+  \bl{$|Seq(v_1,v_2)|$}& \bl{$\dn$} & \bl{$|v_1| \,@\, |v_2|$}\\
+  \bl{$|[v_1,\ldots ,v_n]|$} & \bl{$\dn$} & \bl{$|v_1| \,@\ldots @\, |v_n|$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{textblock}{10}(3,5)
+\begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}]
+\node (r1)  {\bl{$r_1$}};
+\node (r2) [right=of r1] {\bl{$r_2$}};
+\draw[->,line width=1mm]  (r1) -- (r2) node[above,midway] {\bl{$der\,a$}};
+\node (r3) [right=of r2] {\bl{$r_3$}};
+\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};
+\node (r4) [right=of r3] {\bl{$r_4$}};
+\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};
+\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};
+\node (v4) [below=of r4] {\bl{$v_4$}};
+\draw[->,line width=1mm]  (r4) -- (v4);
+\node (v3) [left=of v4] {\bl{$v_3$}};
+\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};
+\node (v2) [left=of v3] {\bl{$v_2$}};
+\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};
+\node (v1) [left=of v2] {\bl{$v_1$}};
+\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};
+\draw[->,line width=0.5mm]  (r3) -- (v3);
+\draw[->,line width=0.5mm]  (r2) -- (v2);
+\draw[->,line width=0.5mm]  (r1) -- (v1);
+\draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}};
+\end{tikzpicture}
+\end{textblock}
+
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6cm]
+\small
+\begin{tabular}{ll}
+\bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\
+\bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\
+\bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\
+\bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+\begin{textblock}{6}(1,11.4)
+\begin{bubble}[7.6cm]
+\small
+\begin{tabular}{ll}
+\bl{$v_1$}: & \bl{$Seq(Char(a), Seq(Char(b), Char(c)))$}\\
+\bl{$v_2$}: & \bl{$Seq(Empty, Seq(Char(b), Char(c)))$}\\
+\bl{$v_3$}: & \bl{$Right(Seq(Empty, Char(c)))$}\\
+\bl{$v_4$}: & \bl{$Right(Right(Empty))$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+\begin{textblock}{6}(12,11.4)
+\begin{bubble}[2cm]
+\small
+\begin{tabular}{ll}
+\bl{$|v_1|$}: & \bl{$abc$}\\
+\bl{$|v_2|$}: & \bl{$bc$}\\
+\bl{$|v_3|$}: & \bl{$c$}\\
+\bl{$|v_4|$}: & \bl{$[]$}
+\end{tabular}
+\end{bubble}
+\end{textblock}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Lexing}
@@ -719,6 +820,57 @@
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Records}
+
+\begin{itemize}
+\item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause
+
+\item \bl{$nullable(x:r) \dn nullable(r)$}
+\item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$}
+\item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$}
+\item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$}
+\end{itemize}\bigskip\bigskip\pause
+
+\small
+for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{itemize}
+\item Regular expression for email addresses
+
+\begin{center}
+\begin{tabular}{l}
+(name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\ 
+\qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,.-]^+$}) \bl{$\cdot .\cdot$}\\ 
+\qquad\qquad(top\_level: \bl{$[a\mbox{-}z\,.]^{\{2,6\}}$})
+\end{tabular}
+\end{center}
+
+\bl{\[
+\texttt{christian.urban@kcl.ac.uk}
+\]}
+
+\item result environment:
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$[(name:\texttt{christian.urban}),$}\\ 
+\bl{$\phantom{[}(domain:\texttt{kcl}),$}\\ 
+\bl{$\phantom{[}(top\_level:\texttt{ac.uk})]$}
+\end{tabular}
+\end{center}
+\end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -740,6 +892,8 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Simplification}
@@ -775,6 +929,11 @@
 \end{tikzpicture}
 \end{center}
 
+\small
+\hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}
+$\mapsto$
+\bl{$\epsilon$}
+
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
@@ -803,6 +962,94 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Rectification}
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$simp(r)$}:\\
+\quad case \bl{$r = r_1 + r_2$}\\
+\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
+\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
+\qquad case \bl{$r_{1s} = \varnothing$}: 
+       return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\
+\qquad case \bl{$r_{2s} = \varnothing$}: 
+       return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
+\qquad case \bl{$r_{1s} = r_{2s}$}:
+       return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\
+\qquad otherwise: 
+       return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\
+\end{tabular}
+\end{center}
+
+\small
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}l}
+\bl{$f_{alt}(f_1, f_2) \dn$}\\
+\qquad \bl{$\lambda v.\,$} case \bl{$v = Left(v')$}: 
+      & return \bl{$Left(f_1(v'))$}\\
+\qquad \phantom{$\lambda v.\,$} case \bl{$v = Right(v')$}: 
+      & return \bl{$Right(f_2(v'))$}\\      
+\end{tabular}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+\begin{frame}[c]
+
+{\footnotesize\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app05.scala}}
+
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Rectification}
+
+\begin{center}
+\begin{tabular}{@{\hspace{-3mm}}l}
+\bl{$simp(r)$}:\ldots\\
+\quad case \bl{$r = r_1 \cdot r_2$}\\
+\qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\
+\qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\
+\qquad case \bl{$r_{1s} = \varnothing$}: 
+       return \bl{$(\varnothing, f_{error})$}\\
+\qquad case \bl{$r_{2s} = \varnothing$}: 
+       return \bl{$(\varnothing, f_{error})$}\\
+\qquad case \bl{$r_{1s} = \epsilon$}: 
+return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\
+\qquad case \bl{$r_{2s} = \epsilon$}: 
+return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\
+\qquad otherwise: 
+       return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\
+\end{tabular}
+\end{center}
+
+\small
+\begin{center}
+\begin{tabular}{l@{\hspace{1mm}}l}
+\bl{$f_{seq}(f_1, f_2) \dn$}\\
+\qquad \bl{$\lambda v.\,$ case $v = Seq(v_1, v_2)$}: 
+      & return \bl{$Seq(f_1(v_1), f_2(v_2))$}\\
+\end{tabular}
+\end{center}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+
+
+\begin{frame}[c]
+
+{\footnotesize\lstinputlisting[language=Scala,numbers=none,
+xleftmargin=-5mm] {../progs/app06.scala}}
+
+\end{frame}
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{Lexing with Simplification}
@@ -844,6 +1091,29 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+$zeroable(\varnothing)$      & $\dn$ & $true$\\
+$zeroable(\epsilon)$           & $\dn$ &  $f\!alse$\\
+$zeroable (c)$                    & $\dn$ &  $f\!alse$\\
+$zeroable (r_1 + r_2)$        & $\dn$ &  $zeroable(r_1) \wedge zeroable(r_2)$ \\ 
+$zeroable (r_1 \cdot r_2)$  & $\dn$ &  $zeroable(r_1) \vee zeroable(r_2)$ \\
+$zeroable (r^*)$                  & $\dn$ & $f\!alse$\\
+\end{tabular}
+\end{center}
+
+\begin{center}
+$zeroable(r)$ if and only if $L(r) = \varnothing$
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
 \end{document}
 
 %%% Local Variables: