
diff -r 4deef8ac5d72 -r 332fbe9c91ab slides/slides03.tex
--- a/slides/slides03.tex	Sun Oct 05 23:56:18 2014 +0100
+++ b/slides/slides03.tex	Mon Oct 06 00:46:18 2014 +0100
@@ -1,41 +1,22 @@
 \documentclass[dvipsnames,14pt,t]{beamer}
-\usepackage{beamerthemeplaincu}
-\usepackage[absolute,overlay]{textpos}
-\usepackage{ifthen}
-\usepackage{tikz}
-\usepackage{pgf}
-\usepackage{calc} 
-\usepackage{ulem}
-\usepackage{courier}
-\usepackage{listings}
-\renewcommand{\uline}[1]{#1}
-\usetikzlibrary{arrows}
-\usetikzlibrary{automata}
-\usetikzlibrary{shapes}
-\usetikzlibrary{shadows}
-\usetikzlibrary{positioning}
-\usetikzlibrary{calc}
-\usetikzlibrary{fit}
-\usetikzlibrary{backgrounds}
-\usepackage{graphicx} 
+\usepackage{../slides}
+\usepackage{../graphics}
 \usepackage{../langs}
 \usepackage{../data}
 
-\makeatletter
-\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
-\@empty\z@\@empty
-\makeatother
+\hfuzz=220pt 
+
+\pgfplotsset{compat=1.11}
+
+\newcommand{\bl}[1]{\textcolor{blue}{#1}}  
 
 % beamer stuff 
-\renewcommand{\slidecaption}{AFL 03, King's College London, 9.~October 2013}
-\newcommand{\bl}[1]{\textcolor{blue}{#1}}       
-\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
+\renewcommand{\slidecaption}{AFL 03, King's College London}
 
 \begin{document}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}<1>[t]
+\begin{frame}[t]
 \frametitle{%
   \begin{tabular}{@ {}c@ {}}
   \\[-3mm]
@@ -43,12 +24,6 @@
   \LARGE Formal Languages (3)\\[3mm] 
   \end{tabular}}
 
-  %\begin{center}
-  %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}
-  %\includegraphics[scale=0.31]{pics/ante2.jpg}\\
-  %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}
-  %\end{center}
-
 \normalsize
   \begin{center}
   \begin{tabular}{lp{8cm}}
@@ -58,12 +33,10 @@
   \end{tabular}
   \end{center}
 
-
-\end{frame}}
+\end{frame}
  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
 
@@ -77,35 +50,32 @@
 \item comments
 \end{itemize}\bigskip
 
-
 \mbox{}\hfill\bl{\url{http://www.regexper.com}}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Last Week\end{tabular}}
+\frametitle{Last Week}
 
 Last week I showed you a regular expression matcher 
-which works provably correctly in all cases.
+which works provably correct in all cases (we did not
+do the proving part though)
 
 \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}\bigskip\bigskip 
 
 \small
 \textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}
 
-  
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}
+\frametitle{The Derivative of a Rexp}
 
 \begin{center}
 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
@@ -116,69 +86,62 @@
   \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\\
+  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\
 
-  \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}
 
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 
-
 To see what is going on, define
 
 \begin{center}
 \bl{$Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 
 \end{center}\bigskip\bigskip
 
-\small
-For \bl{$A = \{"f\!oo", "bar", "f\!rak"\}$} then
+For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then
 
 \begin{center}
 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l}
-$Der\,f\,A$ & $=$ & $\{"oo", "rak"\}$\\
-$Der\,b\,A$ & $=$ &  $\{"ar"\}$\\  
+$Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\
+$Der\,b\,A$ & $=$ &  $\{\textit{ar}\}$\\  
 $Der\,a\,A$ & $=$ & $\varnothing$\\
 \end{tabular}}
 \end{center}
  
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}The Idea of the Algorithm\end{tabular}}
+\frametitle{The Idea of the Algorithm}
 
-If we want to recognise the string \bl{$"abc"$} with regular expression \bl{$r$}
+If we want to recognise the string \bl{$abc$} with regular expression \bl{$r$}
 then\medskip
 
 \begin{enumerate}
 \item \bl{$Der\,a\,(L(r))$}\pause
 \item \bl{$Der\,b\,(Der\,a\,(L(r)))$}\pause
-\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\pause
+\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r))))$}\bigskip\pause
 \item finally we test whether the empty string is in this set\pause\medskip
 \end{enumerate}
 
-The matching algorithm works similarly, just over regular expression instead of sets.
-\end{frame}}
+The matching algorithm works similarly, just over regular expressions instead of sets.
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 
-Input: string \bl{$"abc"$} and regular expression \bl{$r$} 
+Input: string \bl{$abc$} and regular expression \bl{$r$} 
 
 \begin{enumerate}
 \item \bl{$der\,a\,r$}
@@ -187,31 +150,28 @@
 \item finally check whether the last regular expression can match the empty string
 \end{enumerate}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 
 We proved already
 
 \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}
 
 by induction on the regular expression.\bigskip\pause
 
 \begin{center}
-\huge\bf \alert{Any Questions?}
+{\huge\bf\alert{Any Questions?}}
 \end{center}
 
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 
 We need to prove
@@ -221,14 +181,13 @@
 \end{center}
 
 by induction on the regular expression.
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}}
+\frametitle{Proofs about Rexps}
 
 \begin{itemize}
 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip
@@ -240,11 +199,10 @@
 holds for \bl{$r$}.
 \end{itemize}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}
 
@@ -255,20 +213,19 @@
 \end{itemize}\bigskip
 
 \begin{itemize}
-\item \bl{$P$} holds for \bl{$""$} and
+\item \bl{$P$} holds for \bl{$[]$} and
 \item \bl{$P$} holds for \bl{$c\!::\!s$} under the assumption that \bl{$P$} already
 holds for \bl{$s$}
 \end{itemize}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Languages\end{tabular}}
+\frametitle{Languages}
 
 A \alert{language} is a set of strings.\bigskip
 
@@ -277,14 +234,13 @@
 A language is \alert{regular} iff there exists
 a regular expression that recognises all its strings.\bigskip\bigskip\pause
 
-\textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$}.}
-\end{frame}}
+\textcolor{gray}{not all languages are regular, e.g.~\bl{$a^nb^n$} is not}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
-\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
+\frametitle{Regular Expressions}
 
 \begin{center}
    \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
@@ -300,16 +256,15 @@
 How about ranges \bl{$[a\mbox{-}z]$}, \bl{$r^+$} and \bl{$\sim{}r$}? Do they increase the
 set of languages we can recognise?
   
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Negation of Regular Expr's\end{tabular}}
+\frametitle{Negation of Regular Expr's}
 
 \begin{itemize}
-\item \bl{$\sim{}r$}  \hspace{6mm} (everything that \bl{r} cannot recognise)\medskip
+\item \bl{$\sim{}r$}  \hspace{6mm} (everything that \bl{$r$} cannot recognise)\medskip
 \item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip
 \item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip
 \item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$}
@@ -321,45 +276,42 @@
 \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /}
 \]
 
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Negation\end{tabular}}
+\frametitle{Negation}
 
-Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only.
-Find a regular expression that matches all strings \emph{except} \bl{ab} and \bl{ac}.
+Assume you have an alphabet consisting of the letters \bl{$a$}, \bl{$b$} and \bl{$c$} only.
+Find a (basic!) regular expression that matches all strings \emph{\alert{except}} 
+\bl{$ab$} and \bl{$ac$}!
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}}
-
-Lexing separates strings into ``words'' / components.
-
-\begin{itemize}
-\item Identifiers (non-empty strings of letters or digits, starting with a letter)
-\item Numbers (non-empty sequences of digits omitting leading zeros)
-\item Keywords (else, if, while, \ldots)
-\item White space (a non-empty sequence of blanks, newlines and tabs)
-\item Comments
-\end{itemize}
-
-\end{frame}}
+%\mode<presentation>{
+%\begin{frame}[c]
+%\frametitle{\begin{tabular}{c}Regular Exp's for Lexing\end{tabular}}
+%
+%Lexing separates strings into ``words'' / components.
+%
+%\begin{itemize}
+%\item Identifiers (non-empty strings of letters or digits, starting with a letter)
+%\item Numbers (non-empty sequences of digits omitting leading zeros)
+%\item Keywords (else, if, while, \ldots)
+%\item White space (a non-empty sequence of blanks, newlines and tabs)
+%\item Comments
+%\end{itemize}
+%
+%\end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}Automata\end{tabular}}
+\frametitle{Automata}
 
 A \alert{deterministic finite automaton} consists of:
 
@@ -370,7 +322,8 @@
 \item there is transition function\medskip 
 
 \small
-which takes a state as argument and a character and produces a new state\smallskip\\
+which takes a state as argument and a character and produces a 
+new state\smallskip\\
 this function might not be everywhere defined
 \end{itemize}
 
@@ -378,12 +331,11 @@
 \bl{$A(Q, q_0, F, \delta)$}
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 
 \begin{center}
@@ -413,11 +365,10 @@
 \item all states might be accepting (but this does not necessarily mean all strings are accepted)
 \end{itemize}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 
 \begin{center}
@@ -449,15 +400,12 @@
 \end{tabular}\ldots
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
-
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
-\frametitle{\begin{tabular}{c}Accepting a String\end{tabular}}
+\frametitle{Accepting a String}
 
 Given
 
@@ -469,7 +417,7 @@
 
 \begin{center}
 \begin{tabular}{l}
-\bl{$\hat{\delta}(q, \texttt{""}) \dn q$}\\
+\bl{$\hat{\delta}(q, []) \dn q$}\\
 \bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\
 \end{tabular}
 \end{center}\pause
@@ -479,11 +427,10 @@
 \begin{center}
 \hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$}
 \end{center}
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}}
 
@@ -508,11 +455,10 @@
 \end{tabular}
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Two NFA Examples}
 
@@ -544,12 +490,10 @@
 \end{tabular}
 \end{center}
 
-
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[c]
 \frametitle{Rexp to NFA}
 
@@ -572,11 +516,10 @@
 \end{tabular}
 \end{center}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
 \frametitle{Case $r_1\cdot r_2$}
 
@@ -620,13 +563,13 @@
 We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them
 via $\epsilon$-transitions to the starting state of the second automaton. 
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
 \begin{frame}[t]
 \frametitle{Case $r_1+ r_2$}
+\mbox{}\\[-10mm]
 
 \onslide<1>{By recursion we are given two automata:\smallskip}
 
@@ -666,7 +609,7 @@
 
 \small
 We (1) need to introduce a new starting state and (2) connect it to the original two starting states.
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -754,6 +697,26 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Regexps and Automata}
+
+\begin{center}
+\begin{tikzpicture}
+\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);}
+\end{tikzpicture}\\
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
@@ -772,48 +735,66 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}<2>[c]
+\frametitle{DFA to Rexp}
+
+\begin{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}
+
+\onslide<3>{How to get from a DFA to a regular expression?}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \mode<presentation>{
-\begin{frame}<1-2>[c]
+\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);
+\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<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] {\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}\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}
-
-\mbox{}\\[-20mm]\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_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}
+}
 
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
@@ -822,6 +803,49 @@
 \mode<presentation>{
 \begin{frame}[c]
 
+\begin{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<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] {\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$}\\
+\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->{
+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]
+
 Given the function 
 
 \begin{center}




