# HG changeset patch
# User Christian Urban <christian dot urban at kcl dot ac dot uk>
# Date 1413139195 -3600
# Node ID 1446bc47a294b0a7e5328e72d9f0e7ff8d7e3b3b
# Parent  b9b54574ee416b997244ee9525d765b3edc45785
updated

diff -r b9b54574ee41 -r 1446bc47a294 coursework/cw01.pdf
Binary file coursework/cw01.pdf has changed
diff -r b9b54574ee41 -r 1446bc47a294 coursework/cw01.tex
--- a/coursework/cw01.tex	Sat Oct 11 13:54:18 2014 +0100
+++ b/coursework/cw01.tex	Sun Oct 12 19:39:55 2014 +0100
@@ -123,13 +123,14 @@
 rules:
 
 \begin{center}
-\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
+\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}ll}
 $r \cdot \varnothing$ & $\mapsto$ & $\varnothing$\\ 
 $\varnothing \cdot r$ & $\mapsto$ & $\varnothing$\\ 
 $r \cdot \epsilon$ & $\mapsto$ & $r$\\ 
 $\epsilon \cdot r$ & $\mapsto$ & $r$\\ 
 $r + \varnothing$ & $\mapsto$ & $r$\\ 
 $\varnothing + r$ & $\mapsto$ & $r$\\ 
+$r + r$ & $\mapsto$ & $r$ & (added on 12 October)\\ 
 \end{tabular}
 \end{center}
 
diff -r b9b54574ee41 -r 1446bc47a294 handouts/ho02.pdf
Binary file handouts/ho02.pdf has changed
diff -r b9b54574ee41 -r 1446bc47a294 handouts/ho02.tex
--- a/handouts/ho02.tex	Sat Oct 11 13:54:18 2014 +0100
+++ b/handouts/ho02.tex	Sun Oct 12 19:39:55 2014 +0100
@@ -7,7 +7,7 @@
 \pgfplotsset{compat=1.11}
 \begin{document}
 
-\section*{Handout 2}
+\section*{Handout 2 (Regular Expression Matching)}
 
 This lecture is about implementing a more efficient regular
 expression matcher (the plots on the right)---more efficient
diff -r b9b54574ee41 -r 1446bc47a294 langs.sty
--- a/langs.sty	Sat Oct 11 13:54:18 2014 +0100
+++ b/langs.sty	Sun Oct 12 19:39:55 2014 +0100
@@ -32,11 +32,12 @@
 }[keywords,comments,strings]
 
 \lstdefinelanguage{While}{
-  morekeywords={if,then,else,while,do,true,false,write,upto,for,skip},
-  otherkeywords={=,!=,:=,<,>,;},
-  sensitive=true,
+  morekeywords={if,then,else,while,do,true,false,write,upto,read,for,skip},
+  morecomment=[l]{//},
   morecomment=[n]{/*}{*/},
-}
+  morestring=[b]",
+  otherkeywords={=,!=,:=,<,>,\%;*,/},
+}[keywords,comments,strings]
 
 \lstdefinestyle{mystyle}
        {basicstyle=\ttfamily,
diff -r b9b54574ee41 -r 1446bc47a294 progs/Matcher2.thy
--- a/progs/Matcher2.thy	Sat Oct 11 13:54:18 2014 +0100
+++ b/progs/Matcher2.thy	Sun Oct 12 19:39:55 2014 +0100
@@ -303,5 +303,5 @@
 by (induct s arbitrary: r)
    (simp_all add: nullable_correctness der_correctness Der_def)
 
-`
+
 end    
\ No newline at end of file
diff -r b9b54574ee41 -r 1446bc47a294 progs/fib.while
--- a/progs/fib.while	Sat Oct 11 13:54:18 2014 +0100
+++ b/progs/fib.while	Sun Oct 12 19:39:55 2014 +0100
@@ -2,7 +2,7 @@
    input: n */
 
 write "Fib";
-read n;   // n := 19;
+read n;  
 minus1 := 0;
 minus2 := 1;
 while n > 0 do {
diff -r b9b54574ee41 -r 1446bc47a294 slides/slides04.pdf
Binary file slides/slides04.pdf has changed
diff -r b9b54574ee41 -r 1446bc47a294 slides/slides04.tex
--- a/slides/slides04.tex	Sat Oct 11 13:54:18 2014 +0100
+++ b/slides/slides04.tex	Sun Oct 12 19:39:55 2014 +0100
@@ -32,11 +32,9 @@
   \end{tabular}
   \end{center}
 \end{frame}
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
-
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Regexps and Automata}
 
@@ -45,62 +43,16 @@
 \node (rexp)  {\bl{\bf Regexps}};
 \node (nfa) [right=of rexp] {\bl{\bf NFAs}};
 \node (dfa) [right=of nfa] {\bl{\bf DFAs}};
-\onslide<3->{\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};}
-\path[->, red, line width=2mm] (rexp) edge node [above=4mm, black] {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);
-\path[->, red, line width=2mm] (nfa) edge node [above=4mm, black] {\begin{tabular}{c}subset\\[-1mm] construction\end{tabular}}(dfa);
-\onslide<3->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}
-\onslide<2->{\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);}
+\node (mdfa) [right=of dfa] {\bl{\bf \begin{tabular}{c}minimal\\ DFAs\end{tabular}}};
+\path[->,red, line width=2mm] (rexp) edge node [above=4mm, black] 
+     {\begin{tabular}{c@{\hspace{9mm}}}Thompson's\\[-1mm] construction\end{tabular}} (nfa);
+\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);
 \end{tikzpicture}\\
 \end{center}
 
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}}
-
-\mbox{}\\[-13mm]
-
-\begin{tikzpicture}[y=.2cm, x=.09cm]
- 	%axis
-	\draw (0,0) -- coordinate (x axis mid) (100,0);
-    	\draw (0,0) -- coordinate (y axis mid) (0,30);
-    	%ticks
-    	\foreach \x in {0,10,...,100}
-     		\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 {nfa.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 NFA 1};		
-	\end{scope}
-\end{tikzpicture}
-
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
@@ -108,45 +60,29 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \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};
+\frametitle{\bl{$(a?\{n\}) \cdot a\{n\}$}}
 
-	%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 {nfasearch.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 NFA 2};		
-	\end{scope}
+\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=10cm,
+    height=7cm, 
+    legend entries={Python,Ruby,my NFA},  
+    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 {nfasearch.data};	  
+\end{axis}
 \end{tikzpicture}
 
 \end{frame}}
@@ -154,105 +90,42 @@
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}<2>[c]
+\begin{frame}[c]
 \frametitle{DFA to Rexp}
 
 \begin{center}
-\begin{tikzpicture}[scale=2, line width=0.5mm]
-  \only<1>{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<2->{\node[state, initial,accepting]        (q0) at ( 0,1) {$q_0$};}
-  \only<1>{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<2->{\node[state,accepting]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
-  \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};}
-  \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
-                  (q1) edge[bend left] node[above] {$b$} (q0)
-                  (q2) edge[bend left=50] node[below] {$b$} (q0)
-                  (q1) edge node[above] {$a$} (q2)
-                  (q2) edge [loop right] node {$a$} ()
-                  (q0) edge [loop below] node {$b$} ()
-            ;
-\end{tikzpicture}
-\end{center}
-
-\onslide<3>{How to get from a DFA to a regular expression?}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\begin{tikzpicture}[scale=2, line width=0.5mm]
-  \only<1->{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<1->{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
-  \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
-                  (q1) edge[bend left] node[above] {$b$} (q0)
-                  (q2) edge[bend left=50] node[below] {$b$} (q0)
-                  (q1) edge node[above] {$a$} (q2)
-                  (q2) edge [loop right] node {$a$} ()
-                  (q0) edge [loop below] node {$b$} ()
-            ;
-\end{tikzpicture}
-\end{center}\pause\bigskip
-
-\onslide<2->{
-\begin{center}
-\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 +  4\, q_2$}\\
-\bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\
-\bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\
-
-\end{tabular}
-\end{center}
-}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-
-\begin{center}
-\begin{tikzpicture}[scale=2, line width=0.5mm]
-  \only<1->{\node[state, initial]        (q0) at ( 0,1) {$q_0$};}
-  \only<1->{\node[state]                    (q1) at ( 1,1) {$q_1$};}
-  \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
-  \path[->] (q0) edge[bend left] node[above] {$a$} (q1)
-                  (q1) edge[bend left] node[above] {$b$} (q0)
-                  (q2) edge[bend left=50] node[below] {$b$} (q0)
-                  (q1) edge node[above] {$a$} (q2)
-                  (q2) edge [loop right] node {$a$} ()
-                  (q0) edge [loop below] node {$b$} ()
-            ;
+\begin{tikzpicture}[scale=2,>=stealth',very thick,
+                    every state/.style={minimum size=0pt,
+                    draw=blue!50,very thick,fill=blue!20},]
+  \node[state, initial]        (q0) at ( 0,1) {$q_0$};
+  \node[state]                    (q1) at ( 1,1) {$q_1$};
+  \node[state, accepting] (q2) at ( 2,1) {$q_2$};
+  \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
+            (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+            (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+            (q1) edge node[above] {\alert{$a$}} (q2)
+            (q2) edge [loop right] node {\alert{$a$}} ()
+            (q0) edge [loop below] node {\alert{$b$}} ();
 \end{tikzpicture}
 \end{center}\bigskip
 
-\onslide<2->{
 \begin{center}
-\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
-\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b +  q_2\,b$}\\
+\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l}
+\bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b +  q_2\,b$} & (start state)\\
 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\
 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\
 
 \end{tabular}
 \end{center}
-}
 
-\onslide<3->{
+\onslide<2->{
 Arden's Lemma:
 \begin{center}
 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
 \end{center}
 }
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -334,11 +207,11 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 
 \begin{center}
+\begin{tabular}{@{\hspace{-8mm}}cc@{}}
 \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$};
@@ -356,8 +229,43 @@
 \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}
+&
+\raisebox{9mm}{\begin{tikzpicture}[scale=0.6,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$};
+\draw (0.5,1.5) node {\large$\star$}; 
+\draw (2.5,1.5) node {\large$\star$}; 
+\draw (0.5,3.5) node {\large$\star$}; 
+\draw (1.5,2.5) node {\large$\star$}; 
+\end{tikzpicture}}
+\end{tabular}
 \end{center}
 
+
 \mbox{}\\[-20mm]\mbox{}
 
 \begin{center}
@@ -378,64 +286,297 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}<1-2>[c]
+\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},]
-\node[state,initial]  (q_0)  {$q_0$};
+                    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$};
-\node[state, accepting] (q_4) [right=of q_1] {$q_4$};
+\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 right] node  {\alert{$a, b$}} ();
+\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);
+\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}\pause
+\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
 
-\mbox{}\\[-20mm]\mbox{}
+\begin{quote}\rm A language is \alert{regular} iff there exists a
+regular expression that recognises all its strings.
+\end{quote}
+
+\begin{quote}\rm A language is \alert{regular} iff there exists an
+automaton that recognises all its strings.
+\end{quote}\bigskip\bigskip
+
+
+\small
+for example $a^nb^n$ is not regular
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Negation}
+
+Regular languages are closed under negation:\bigskip
 
 \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_02)  {$q_{0, 2}$};
-\node[state] (q_13) [right=of q_02] {$q_{1, 3}$};
-\node[state, accepting] (q_4) [right=of q_13] {$q_{4\phantom{,0}}$};
-\path[->] (q_02) edge [bend left] node [above]  {\alert{$a$}} (q_13);
-\path[->] (q_13) edge [bend left] node [below]  {\alert{$b$}} (q_02);
-\path[->] (q_02) edge [loop below] node  {\alert{$b$}} ();
-\path[->] (q_13) edge node [above]  {\alert{$a$}} (q_4);
-\path[->] (q_4) edge [loop above] node  {\alert{$a, b$}} ();
-\end{tikzpicture}\\
-minimal automaton
-\end{center}
+\begin{tikzpicture}[scale=2,>=stealth',very thick,
+                    every state/.style={minimum size=0pt,
+                    draw=blue!50,very thick,fill=blue!20}]
+  \only<1>{\node[state,initial] (q0) at ( 0,1) {$q_0$};}
+  \only<2>{\node[state,initial,accepting] (q0) at ( 0,1) {$q_0$};}
+  \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};}
+  \only<2>{\node[state,accepting] (q1) at ( 1,1) {$q_1$};}
+  \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
+  \only<2>{\node[state] (q2) at ( 2,1) {$q_2$};}
+  \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
+            (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+            (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+            (q1) edge node[above] {\alert{$a$}} (q2)
+            (q2) edge [loop right] node {\alert{$a$}} ()
+            (q0) edge [loop below] node {\alert{$b$}} ();
+\end{tikzpicture}
+\end{center}\bigskip\bigskip
 
-\end{frame}}
+\onslide<2>{But requires that the automaton is \alert{completed}!}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\mbox{\lstinputlisting[language=While]{../progs/fib.while}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{??}
+
+\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}
+
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \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
+\begin{center}\large
+\code{"if true then then 42 else +"}
+\end{center}
+
+
+\begin{tabular}{@{}l}
+KEYWORD: \\
+\hspace{5mm}{if}, {then}, {else},\\ 
+WHITESPACE:\\
+\hspace{5mm}{" "}, {$\backslash$n},\\ 
+IDENT:\\
+\hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + {\_})$^*$\\ 
+NUM:\\
+\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {0}\\
+OP:\\
+\hspace{5mm}{+}\\
+COMMENT:\\
+\hspace{5mm}{$\slash$*} $\cdot$ (ALL$^*$ $\cdot$ {$\sim$(*$\slash$)} $\cdot$ ALL$^*$) $\cdot$ {*$\slash$}
+\end{tabular}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+
+\tt
+\begin{center}\large
+\code{"if true then then 42 else +"}
+\end{center}
+
+\only<1>{
+\small\begin{tabular}{l}
+KEYWORD(if),\\ 
+WHITESPACE,\\ 
+IDENT(true),\\ 
+WHITESPACE,\\ 
+KEYWORD(then),\\ 
+WHITESPACE,\\ 
+KEYWORD(then),\\ 
+WHITESPACE,\\ 
+NUM(42),\\ 
+WHITESPACE,\\ 
+KEYWORD(else),\\ 
+WHITESPACE,\\ 
+OP(+)
+\end{tabular}}
+
+\only<2>{
+\small\begin{tabular}{l}
+KEYWORD(if),\\ 
+IDENT(true),\\ 
+KEYWORD(then),\\ 
+KEYWORD(then),\\ 
+NUM(42),\\ 
+KEYWORD(else),\\ 
+OP(+)
+\end{tabular}}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+
+There is one small problem with the tokenizer. How should we 
+tokenize:
+
+\begin{center}
+\large\code{"x-3"}
+\end{center}
+
+\tt
+\begin{tabular}{@{}l}
+ID: \ldots\\
+OP:\\
+\hspace{5mm}\texttt{"+"}, \texttt{"-"}\\
+NUM:\\
+\hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + {''0''}\\
+NUMBER:\\
+\hspace{5mm}NUM +  (\texttt{"-"} $\cdot$ NUM)\\
+\end{tabular}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{POSIX: Two Rules}
 
 \begin{itemize}
-\item Assuming you have the alphabet \bl{$\{a, b, c\}$}\bigskip
-\item Give a regular expression that can recognise all strings that have at least one \bl{$b$}.
-\end{itemize}
+\item Longest match rule (``maximal munch rule''): The 
+longest initial substring matched by any regular expression is taken
+as next token.\bigskip
+
+\item Rule priority:
+For a particular longest initial substring, the first regular
+expression that can match determines the token.
+\end{itemize}\bigskip\bigskip\pause
+
+\small
+\hfill most posix matchers are buggy\\
+\footnotesize
+\hfill \url{http://www.haskell.org/haskellwiki/Regex_Posix}
+
+%\url{http://www.technologyreview.com/tr10/?year=2011}  
+%finite deterministic automata/ nondeterministic automaton
+%\item problem with infix operations, for example i-12
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Sulzmann Matcher}
+
+We want to match the string \bl{$abc$} using \bl{$r_1$}:
 
-\end{frame}}
+\begin{center}
+\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$}};\pause
+\node (r3) [right=of r2] {\bl{$r_3$}};
+\draw[->,line width=1mm]  (r2) -- (r3) node[above,midway] {\bl{$der\,b$}};\pause
+\node (r4) [right=of r3] {\bl{$r_4$}};
+\draw[->,line width=1mm]  (r3) -- (r4) node[above,midway] {\bl{$der\,c$}};\pause
+\draw (r4) node[anchor=west] {\;\raisebox{3mm}{\bl{$nullable$}}};\pause
+\node (v4) [below=of r4] {\bl{$v_4$}};
+\draw[->,line width=1mm]  (r4) -- (v4);\pause
+\node (v3) [left=of v4] {\bl{$v_3$}};
+\draw[->,line width=1mm]  (v4) -- (v3) node[below,midway] {\bl{$inj\,c$}};\pause
+\node (v2) [left=of v3] {\bl{$v_2$}};
+\draw[->,line width=1mm]  (v3) -- (v2) node[below,midway] {\bl{$inj\,b$}};\pause
+\node (v1) [left=of v2] {\bl{$v_1$}};
+\draw[->,line width=1mm]  (v2) -- (v1) node[below,midway] {\bl{$inj\,a$}};\pause
+\draw[->,line width=0.5mm]  (r3) -- (v3);
+\draw[->,line width=0.5mm]  (r2) -- (v2);
+\draw[->,line width=0.5mm]  (r1) -- (v1);
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
 \end{document}
 
 %%% Local Variables:  
diff -r b9b54574ee41 -r 1446bc47a294 slides/slides05.tex
--- a/slides/slides05.tex	Sat Oct 11 13:54:18 2014 +0100
+++ b/slides/slides05.tex	Sun Oct 12 19:39:55 2014 +0100
@@ -58,8 +58,7 @@
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}<1>[c]
+\begin{frame}[c]
 
 \begin{center}
 \begin{tikzpicture}[>=stealth',very thick,auto,
@@ -114,12 +113,11 @@
 \end{tikzpicture}\\
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}<1-2>[c]
+\begin{frame}[c]
 
 \begin{center}
 \begin{tabular}{@{\hspace{-8mm}}cc@{}}
@@ -194,7 +192,7 @@
 minimal automaton
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%