
diff -r 155426396b5f -r f063a6cd5d91 slides/slides03.tex
--- a/slides/slides03.tex	Thu Jul 30 13:50:54 2020 +0100
+++ b/slides/slides03.tex	Sat Aug 15 14:18:37 2020 +0100
@@ -1,5 +1,5 @@
 % !TEX program = xelatex
-\documentclass[dvipsnames,14pt,t]{beamer}
+\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
 \usepackage{../slides}
 \usepackage{../graphics}
 \usepackage{../langs}
@@ -22,17 +22,33 @@
   \begin{tabular}{@ {}c@ {}}
   \\[-3mm]
   \LARGE Compilers and \\[-2mm] 
-  \LARGE Formal Languages (3)\\[3mm] 
+  \LARGE Formal Languages\\[3mm] 
   \end{tabular}}
 
   \normalsize
   \begin{center}
   \begin{tabular}{ll}
     Email:  & christian.urban at kcl.ac.uk\\
-    Office Hours: & Thursdays 12 -- 14\\
-    Location: & N7.07 (North Wing, Bush House)\\
+    %Office Hours: & Thursdays 12 -- 14\\
+    %Location: & N7.07 (North Wing, Bush House)\\
     Slides \& Progs: & KEATS (also homework is there)\\  
   \end{tabular}
+\end{center}
+
+  \begin{center}
+    \begin{tikzpicture}
+      \node[drop shadow,fill=white,inner sep=0pt] 
+      {\footnotesize\rowcolors{1}{capri!10}{white}
+        \begin{tabular}{|p{4.8cm}|p{4.8cm}|}\hline
+          1 Introduction, Languages          & 6 While-Language \\
+          2 Regular Expressions, Derivatives & 7 Compilation, JVM \\
+          \cellcolor{blue!50}
+          3 Automata, Regular Languages      & 8 Compiling Functional Languages \\
+          4 Lexing, Tokenising               & 9 Optimisations \\
+          5 Grammars, Parsing                & 10 LLVM \\ \hline
+        \end{tabular}%
+      };
+    \end{tikzpicture}
   \end{center}
 
 \end{frame}
@@ -55,206 +71,6 @@
 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Last Week}
-
-Last week I showed you a regular expression matcher 
-that works provably correct in all cases (we only
-started with the proving part though)
-
-\begin{center}
-\bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}
-\end{center}\bigskip\bigskip 
-
-\small
-\textcolor{gray}{\mbox{}\hfill{}by Janusz Brzozowski (1964)}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Derivative of a Rexp}
-
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
-  \bl{$der\, c\, (\ZERO)$}      & \bl{$\dn$} & \bl{$\ZERO$} & \\
-  \bl{$der\, c\, (\ONE)$}           & \bl{$\dn$} & \bl{$\ZERO$} & \\
-  \bl{$der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
-  \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{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^*)$} &\medskip\\
-
-  \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}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Example}
-
-Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
-
-\begin{center}
-\def\arraystretch{1.5}  
-\begin{tabular}{@{}lcl}
-  \bl{$\der\,a\,((a \cdot b) + b)^*$}
-    & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
-    & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
-    & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
-    & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
-    & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
-    & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-Input: string \bl{$abc$} and regular expression \bl{$r$} 
-
-\begin{enumerate}
-\item \bl{$der\,a\,r$}
-\item \bl{$der\,b\,(der\,a\,r)$}
-\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
-\item finally check whether the last regular expression can match the empty string
-\end{enumerate}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Simplification}
-
-Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
-
-\begin{center}
-\def\arraystretch{2}  
-\begin{tabular}{@{}lcl}
-  \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
-    & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
-    & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
-    & \bl{$=$} & \bl{$b \cdot r$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-  \frametitle{Proofs about Rexp}
-  
-  \begin{itemize}
-  \item \bl{$P$} holds for \bl{$\ZERO$}, \bl{$\ONE$} 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$}.\bigskip
-  \item \bl{$P$} holds for \bl{$r^*$} under the assumption that \bl{$P$} already
-  holds for \bl{$r$}.
-  \end{itemize}
-  
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-We proved
-
-\begin{center}
-\bl{$nullable(r)$} \;if and only if\;  \bl{$[] \in L(r)$}
-\end{center}
-
-by induction on the regular expression \bl{$r$}.\bigskip\pause
-
-\begin{center}
-{\huge\bf\alert{Any Questions?}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Proofs about Natural\\[-1mm] Numbers and Strings\end{tabular}}
-
-\begin{itemize}
-\item \bl{$P$} holds for \bl{$0$} and
-\item \bl{$P$} holds for \bl{$n + 1$} under the assumption that \bl{$P$} already
-holds for \bl{$n$}
-\end{itemize}\bigskip
-
-\begin{itemize}
-\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}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-  
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-  \frametitle{Correctness Proof \\[-1mm]
-              for our Matcher}
-  
-  \begin{itemize}
-  \item We started from
-  
-  \begin{center}
-  \begin{tabular}{rp{4cm}}
-    & \bl{$s \in L(r)$}\medskip\\
-  \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause  
-  \end{tabular}
-  \end{center}\bigskip
-  
-  \item \textbf{\alert{if}} we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we 
-  have\bigskip
-  
-  \begin{center}
-  \begin{tabular}{rp{4cm}}
-  \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
-  \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
-  \bl{$\dn$} & \bl{$matches\,s\,r$}
-  \end{tabular}
-  \end{center}
-  
-  \end{itemize}
-  
-  \end{frame}
-  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-
-We need to prove
-
-\begin{center}
-\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
-\end{center}
-
-also by induction on the regular expression \bl{$r$}.
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
 \frametitle{(Basic) Regular Expressions}
 
@@ -1329,6 +1145,360 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\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<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+  \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}                           
+  \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+  \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+  \node[state] (q2) at ( 2,1) {$\mbox{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
+
+\begin{center}
+\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b +  \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\
+\end{tabular}
+\end{center}
+
+
+Arden's Lemma:
+\begin{center}
+If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
+\end{center}
+
+\only<2-6>{\small
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b +  \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<3-6>{\small
+\begin{textblock}{6}(2,4.15)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<4-6>{\small
+\begin{textblock}{6}(3,7.55)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+  \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<5-6>{\small
+\begin{textblock}{6}(4,10.9)
+\begin{bubble}[7.5cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+  \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<6>{\small
+\begin{textblock}{6}(5,13.4)
+\begin{bubble}[7.5cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+  \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+
+\only<7->{\small
+\begin{textblock}{6}(6,11.5)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{Finally:}\\    
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\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}};
+\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);
+\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}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
+
+\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}
+
+The punchline is that many existing libraries do depth-first search
+in NFAs (backtracking).
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \begin{frame}[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},]
+%   \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
+
+% \begin{center}
+% \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l}
+% \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + 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}
+
+% Arden's Lemma:
+% \begin{center}
+% If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
+% \end{center}
+
+
+% \end{frame}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% \begin{frame}[c]
+% \frametitle{DFA Minimisation}
+
+% \begin{enumerate}
+% \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$}
+% \item Mark all pairs that accepting and non-accepting states
+% \item For  all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} test whether
+% \begin{center}
+% \bl{$(\delta(q, c), \delta(p,c))$}
+% \end{center} 
+% are marked. If yes, then also mark \bl{$(q, p)$}.
+% \item Repeat last step until no change.
+% \item All unmarked pairs can be merged.
+% \end{enumerate}
+
+% \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$};
+% \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}
+% &
+% \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}
+% \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}
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Regular Languages}
+
+Two equivalent definitions:\bigskip
+
+\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 \bl{$a^nb^n$} is not regular
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Negation}
+
+Regular languages are closed under negation:\bigskip
+
+\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}\bigskip\bigskip
+
+But requires that the automaton is \alert{completed}!
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
 \end{document}
 
 %%% Local Variables:  




