--- 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}