% !TEX program = xelatex
\documentclass[dvipsnames,14pt,t,xelatex,aspectratio=169,xcolor={table}]{beamer}
\usepackage{../slides}
\usepackage{../graphicss}
\usepackage{../langs}
\usepackage{../data}
\usepackage{tcolorbox}
\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
\hfuzz=220pt
\pgfplotsset{compat=1.17}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
% beamer stuff
\renewcommand{\slidecaption}{CFL 03, King's College London}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Compilers and \\[-1mm]
\LARGE Formal Languages\\[-5mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
Office Hour: & Fridays 11 -- 12\\
Location: & N7.07 (North Wing, Bush House)\\
Slides \& Progs: & KEATS\\
Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\
\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%\frametitle{Scala Book, Exams}
%
%\begin{itemize}
%\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize
%\item homework (written exam 80\%)
%\item coursework (20\%)\bigskip
%\item short survey at KEATS; to be answered until Sunday
%\end{itemize}
%\end{frame}
%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{(Basic) Regular Expressions}
\begin{center}
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
\bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\
& \bl{$\mid$} & \bl{$\ONE$} & empty string / "" / $[]$\\
& \bl{$\mid$} & \bl{$c$} & character\\
& \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
& \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\
& \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\
\end{tabular}
\end{center}
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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Negation}
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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Automata}
A \alert{\bf deterministic finite automaton}, DFA, consists of:
\begin{itemize}
\item an alphabet \bl{$\varSigma$}
\item a set of states \bl{$\mbox{Qs}$}
\item one of these states is the start state \bl{$\mbox{Q}_0$}
\item some states are accepting states \bl{$F$}, and
\item there is transition function \bl{$\delta$}\bigskip
\small
which takes a state as argument and a character and produces a
new state; this function might not be everywhere defined $\Rightarrow$ partial function
\end{itemize}
\begin{center}
\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
every state/.style={minimum size=0pt,inner sep=2pt,
draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (Q_0) {$\mbox{Q}_0$};
\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
\path[->] (Q_0) edge node [above] {\alert{$a$}} (Q_1);
\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_4);
\path[->] (Q_4) edge [loop right] node {\alert{$a, b$}} ();
\path[->] (Q_3) edge node [right] {\alert{$a$}} (Q_4);
\path[->] (Q_2) edge node [above] {\alert{$a$}} (Q_3);
\path[->] (Q_1) edge node [right] {\alert{$b$}} (Q_2);
\path[->] (Q_0) edge node [above] {\alert{$b$}} (Q_2);
\path[->] (Q_2) edge [loop left] node {\alert{$b$}} ();
\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0);
\end{tikzpicture}
\end{center}
\mbox{}\\[-14mm]
\only<1>{
\begin{itemize}
\item the start state can be an accepting state
\item it is possible that there is no accepting state
\item all states might be accepting (but this does not necessarily mean all strings are accepted)
\end{itemize}}
\only<2>{
for this automaton \bl{$\delta$} is the function\\
\begin{center}
\begin{tabular}{lll}
\bl{$(\mbox{Q}_0, a) \rightarrow \mbox{Q}_1$} & \bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_4$}
& \bl{$(\mbox{Q}_4, a) \rightarrow \mbox{Q}_4$}\\
\bl{$(\mbox{Q}_0, b) \rightarrow \mbox{Q}_2$} & \bl{$(\mbox{Q}_1, b) \rightarrow \mbox{Q}_2$} &
\bl{$(\mbox{Q}_4, b) \rightarrow \mbox{Q}_4$}\\
\end{tabular}\ldots
\end{center}
}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Accepting a String}
Given
\begin{center}
\bl{$A(\varSigma, \mbox{Qs}, \mbox{Q}_0, F, \delta)$}
\end{center}
you can define
\begin{center}
\begin{tabular}{l}
\bl{$\widehat{\delta}(Q, []) \dn Q$}\\
\bl{$\widehat{\delta}(Q, c::s) \dn \widehat{\delta}(\delta(Q, c), s)$}\\
\end{tabular}
\end{center}\pause
Whether a string \bl{$s$} is accepted by \bl{$A$}?
\begin{center}
\hspace{5mm}\bl{$\widehat{\delta}(\mbox{Q}_0, s) \in F$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regular Languages}
A \alert{\bf language} is a set of strings.\bigskip
A \alert{\bf regular expression} specifies a language.\bigskip
A language is \alert{\bf regular} iff there exists
a regular expression that recognises all its strings.\bigskip\bigskip\pause
not all languages are regular, e.g.~\bl{$a^nb^n$} is not
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regular Languages (2)}
A language is \alert{\bf regular} iff there exists a regular
expression that recognises all its strings.\bigskip\medskip
or {\bf equivalently}\bigskip\medskip
A language is \alert{\bf regular} iff there exists a
deterministic finite automaton that recognises all its
strings.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\begin{tabular}{c}
Non-Deterministic\\[-1mm]
Finite Automata\end{tabular}}
\bl{$N(\varSigma, \mbox{Qs}, \mbox{Qs}_0, F, \rho)$}\\
A non-deterministic finite automaton (NFA) consists of:
\begin{itemize}
\item a finite set of states, \bl{$Qs$}
\item \underline{some} these states are the start states, \bl{$Qs_0$}
\item some states are accepting states, and
\item there is transition \alert{relation}, \bl{$\rho$}\medskip
\end{itemize}
\begin{center}
\begin{tabular}{c}
\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_2$}\\
\bl{$(\mbox{Q}_1, a) \rightarrow \mbox{Q}_3$}\\
\end{tabular}
\bl{\ldots}
\hspace{10mm}\pause
\bl{$(\mbox{Q}_1, a) \rightarrow \{\mbox{Q}_2, \mbox{Q}_3\}$}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{An NFA Example}
% A NFA for (ab* + b)*a
\begin{center}
\begin{tikzpicture}[>=stealth',very thick, auto,
every state/.style={minimum size=0pt,inner sep=3pt,
draw=blue!50,very thick,fill=blue!20},scale=2]
\node[state,initial] (Q_0) {$\mbox{Q}_0$};
\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
\node[state, accepting] (Q_2) [right=of Q_1] {$\mbox{Q}_2$};
\path[->] (Q_0) edge [loop above] node {\alert{$b$}} ();
\path[<-] (Q_0) edge node [below] {\alert{$b$}} (Q_1);
\path[->] (Q_0) edge [bend left] node [above] {\alert{$a$}} (Q_1);
\path[->] (Q_0) edge [bend right] node [below] {\alert{$a$}} (Q_2);
\path[->] (Q_1) edge [loop above] node {\alert{$a,b$}} ();
\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_2);
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Another Example}
For the regular expression \bl{$(.^*)a\,(.^{\{n\}})bc$}\bigskip\bigskip
% \begin{center}
\mbox{}\hspace{-11.5mm}
\begin{tikzpicture}[>=stealth',very thick, auto,
every state/.style={minimum size=5pt,inner sep=1pt,
draw=blue!50,very thick,fill=blue!20},scale=1, node distance=5mm,
decoration={brace,mirror,amplitude=7}]
\node[state,initial] (Q_0) {$\;0\;$};
\node[state] (Q_1) [right=of Q_0] {$\;1\;$};
\node[state] (Q_2) [right=of Q_1] {$\;2\;$};
\node (Q_3) [right=of Q_2] {$\hspace{-1mm}\ldots\hspace{-3mm}$};
\node[state] (Q_4) [right=of Q_3] {$\;\phantom{1}\;$};
\node (Q_5) [right=of Q_4] {$\hspace{-1mm}\ldots\hspace{-3mm}$};
\node[state] (Q_6) [right=of Q_5] {\tiny$n+1$};
\node[state] (Q_7) [right=of Q_6] {\tiny$n+2$};
\node[state,accepting] (Q_8) [right=of Q_7] {\tiny$n+3$};
\path[->] (Q_0) edge [loop above] node {$*$} ();
\path[->] (Q_0) edge node [above] {$a$} (Q_1);
\path[->] (Q_1) edge node [above] {$*$} (Q_2);
\path[->] (Q_2) edge node [above] {$*$} (Q_3);
\path[->] (Q_4) edge node [above] {$*$} (Q_5);
\path[->] (Q_5) edge node [above] {$*$} (Q_6);
\path[->] (Q_6) edge node [above] {$b$} (Q_7);
\path[->] (Q_7) edge node [above] {$c$} (Q_8);
\draw [decorate] ([yshift=-5mm]Q_1.east) --node[below=3mm]{$n$} ([yshift=-5mm]Q_6.west);
\end{tikzpicture}\bigskip
{\small Note the star-transitions: accept any character.}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Two Epsilon NFA Examples}
\small
\begin{center}
\begin{tabular}[t]{c@{\hspace{9mm}}c}
\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (q_0) {$q_0$};
\node[state] (q_1) [above=of q_0] {$q_1$};
\node[state, accepting] (q_2) [below=of q_0] {$q_2$};
\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1);
\path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2);
\path[->] (q_0) edge [loop right] node {\alert{$a$}} ();
\path[->] (q_1) edge [loop above] node {\alert{$a$}} ();
\path[->] (q_2) edge [loop below] node {\alert{$b$}} ();
\end{tikzpicture} &
\raisebox{20mm}{
\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (r_1) {$r_1$};
\node[state] (r_2) [above=of r_1] {$r_2$};
\node[state, accepting] (r_3) [right=of r_1] {$r_3$};
\path[->] (r_1) edge node [below] {\alert{$b$}} (r_3);
\path[->] (r_2) edge [bend left] node [above] {\alert{$a$}} (r_3);
\path[->] (r_1) edge [bend left] node [left] {\alert{$\epsilon$}} (r_2);
\path[->] (r_2) edge [bend left] node [right] {\alert{$a$}} (r_1);
\end{tikzpicture}}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Thompson: Rexp to $\epsilon$NFA}
\begin{center}
\begin{tabular}[t]{l@{\hspace{10mm}}l}
\raisebox{1mm}{\bl{$\ZERO$}} &
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node[state, initial] (Q_0) {$\mbox{}$};
\end{tikzpicture}\\\\
\raisebox{1mm}{\bl{$\ONE$}} &
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node[state, initial, accepting] (Q_0) {$\mbox{}$};
\end{tikzpicture}\\\\
\raisebox{5mm}{\bl{$c$}} &
\begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node[state, initial] (Q_0) {$\mbox{}$};
\node[state, accepting] (Q_1) [right=of Q_0] {$\mbox{}$};
\path[->] (Q_0) edge node [below] {\alert{$c$}} (Q_1);
\end{tikzpicture}\\\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Case $r_1\cdot r_2$}
\mbox{}\bigskip
\onslide<1->{By recursion we are given two automata:\bigskip}
{\centering%
\only<1>{%
\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick,
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20}]
\node[state, initial] (Q_0) {$\mbox{}$};
\node[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
\node (R_1) [right=of Q_0] {$\ldots$};
\node[state, accepting] (T_1) [right=of R_1] {$\mbox{}$};
\node[state, accepting] (T_2) [above=of T_1] {$\mbox{}$};
\node[state, accepting] (T_3) [below=of T_1] {$\mbox{}$};
\node (A_0) [right=2.5cm of T_1] {$\mbox{}$};
\node[state, initial] (A_01) [above=1mm of A_0] {$\mbox{}$};
\node[state, initial] (A_02) [below=1mm of A_0] {$\mbox{}$};
\node (b_1) [right=of A_0] {$\ldots$};
\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
\begin{pgfonlayer}{background}
\node (1) [rounded corners, inner sep=1mm, thick,
draw=black!60, fill=black!20, fit= (Q_0) (R_1) (T_1) (T_2) (T_3)] {};
\node (2) [rounded corners, inner sep=1mm, thick,
draw=black!60, fill=black!20, fit= (A_0) (b_1) (c_1) (c_2) (c_3)] {};
\node [yshift=2mm] at (1.north) {$r_1$};
\node [yshift=2mm] at (2.north) {$r_2$};
\end{pgfonlayer}
\end{tikzpicture}}
\only<2>{%
\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick,
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\node[state, initial] (Q_0) {$\mbox{}$};
\node[state, initial] (Q_01) [below=1mm of Q_0] {$\mbox{}$};
\node[state, initial] (Q_02) [above=1mm of Q_0] {$\mbox{}$};
\node (r_1) [right=of Q_0] {$\ldots$};
\node[state] (t_1) [right=of r_1] {$\mbox{}$};
\node[state] (t_2) [above=of t_1] {$\mbox{}$};
\node[state] (t_3) [below=of t_1] {$\mbox{}$};
\node (A_0) [right=2.5cm of t_1] {$\mbox{}$};
\node[state] (A_01) [above=1mm of A_0] {$\mbox{}$};
\node[state] (A_02) [below=1mm of A_0] {$\mbox{}$};
\node (b_1) [right=of A_0] {$\ldots$};
\node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$};
\node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$};
\node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$};
\path[->] (t_1) edge (A_01);
\path[->] (t_2) edge node [above] {$\epsilon$s} (A_01);
\path[->] (t_3) edge (A_01);
\path[->] (t_1) edge (A_02);
\path[->] (t_2) edge (A_02);
\path[->] (t_3) edge node [below] {$\epsilon$s} (A_02);
\begin{pgfonlayer}{background}
\node (3) [rounded corners, inner sep=1mm, thick,
draw=black!60, fill=black!20, fit= (Q_0) (c_1) (c_2) (c_3)] {};
\node [yshift=2mm] at (3.north) {$r_1\cdot r_2$};
\end{pgfonlayer}
\end{tikzpicture}}
%
}\bigskip\bigskip
\small
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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Case $r_1+ r_2$}
\mbox{}\\[-8mm]
\onslide<1->{By recursion we are given two automata:\smallskip}
\hspace{2cm}
\only<1>{%
\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick,
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
baseline=(current bounding box.center)]
\node at (0,0) (1) {$\mbox{}$};
\node (2) [above=14mm of 1] {};
\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
\node[state, initial] (3) [below=10mm of 1] {$\mbox{}$};
\node (a) [right=of 2] {$\ldots\,$};
\node (a1) [right=of a] {$$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
\node (b) [right=of 3] {$\ldots$};
\node[state, accepting] (b1) [right=of b] {$\mbox{}$};
\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
\begin{pgfonlayer}{background}
\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};
\node [yshift=3mm] at (1.north) {$r_1$};
\node [yshift=3mm] at (2.north) {$r_2$};
\end{pgfonlayer}
\end{tikzpicture}}
\only<2>{%
\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick,
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
baseline=(current bounding box.center)]
\node at (0,0) (1) {$\mbox{}$};
\node (2) [above=14mm of 1] {$$};
\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
\node[state, initial] (3) [below=10mm of 1] {$\mbox{}$};
\node (a) [right=of 2] {$\ldots\,$};
\node (a1) [right=of a] {$$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
\node (b) [right=of 3] {$\ldots$};
\node[state, accepting] (b1) [right=of b] {$\mbox{}$};
\node[state, accepting] (b2) [above=of b1] {$\mbox{}$};
\node[state, accepting] (b3) [below=of b1] {$\mbox{}$};
%\path[->] (1) edge node [above] {$\epsilon$} (2);
%\path[->] (1) edge node [below] {$\epsilon$} (3);
\begin{pgfonlayer}{background}
\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};
\node [yshift=3mm] at (3.north) {$r_1+ r_2$};
\end{pgfonlayer}
\end{tikzpicture}}
%
\small
\mbox{}\\\medskip
We can just put both automata together.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Case $r^*$}
\onslide<1->{By recursion we are given an automaton for $r$:\smallskip}
\hspace{2cm}
\only<1>{\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick,
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
baseline=(current bounding box.north)]
\node (2) {$\mbox{}$};
\node[state, initial] (4) [above=1mm of 2] {$\mbox{}$};
\node[state, initial] (5) [below=1mm of 2] {$\mbox{}$};
\node (a) [right=of 2] {$\ldots$};
\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};
\begin{pgfonlayer}{background}
\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};
\node [yshift=3mm] at (1.north) {$r$};
\end{pgfonlayer}
\end{tikzpicture}}
\only<2->{\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick,
every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},
baseline=(current bounding box.north)]
\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};
\node (2) [right=16mm of 1] {$\mbox{}$};
\node[state] (4) [above=1mm of 2] {$\mbox{}$};
\node[state] (5) [below=1mm of 2] {$\mbox{}$};
\node (a) [right=of 2] {$\ldots$};
\node[state] (a1) [right=of a] {$\mbox{}$};
\node[state] (a2) [above=of a1] {$\mbox{}$};
\node[state] (a3) [below=of a1] {$\mbox{}$};
\path[->] (1) edge node [below] {$\epsilon$} (4);
\path[->] (1) edge node [below] {$\epsilon$} (5);
\path[->] (a1) edge [bend left=45] node [below] {$\epsilon$} (1);
\path[->] (a2) edge [bend right] node [below] {$\epsilon$} (1);
\path[->] (a3) edge [bend left=45] node [below] {$\epsilon$} (1);
\begin{pgfonlayer}{background}
\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};
\node [yshift=3mm] at (2.north) {$r^*$};
\end{pgfonlayer}
\end{tikzpicture}}
\bigskip
\onslide<3->{
Why can't we just have an epsilon transition from the accepting states to the starting state?}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\mbox{NFA Breadth-First: \boldmath{}$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=9cm,
height=6cm,
legend entries={Python,Ruby,my NFA},
legend pos=outer north east,
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=red}] table {nfabreadth.data};
\end{axis}
\end{tikzpicture}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{NFA Breadth-First:\boldmath{}$(a^*)^* \cdot b$}
\bigskip
\begin{center}
\begin{tikzpicture}
\begin{axis}[
xlabel={\pcode{a}s},
%%x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,10,...,100},
xmax=103,
ymax=35,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
width=9cm,
height=6cm,
legend entries={Java 8,Python,JavaScript,Swift,Dart,my NFA},
legend pos=outer north east,
legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
\addplot[red,mark=triangle*, mark options={fill=red}] table {nfabreadth2.data};
\end{axis}
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{NFA Depth-First: \boldmath$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=9cm,
height=6cm,
legend entries={Python,Ruby,my NFA},
legend pos=outer north east,
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=red}] table {nfadepth.data};
\end{axis}
\end{tikzpicture}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{NFA Depth-First: \boldmath$(a^*)^* \cdot b$}
\bigskip
\begin{center}
\begin{tikzpicture}
\begin{axis}[
xlabel={\pcode{a}s},
%%x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,15,...,30},
xmax=33,
ymax=35,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
width=9cm,
height=6cm,
legend entries={Java 8,Python,JavaScript,Swift,Dart,my NFA},
legend pos=outer north east,
legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
\addplot[red,mark=triangle*, mark options={fill=red}] table {nfadepth2.data};
\end{axis}
\end{tikzpicture}
\end{center}
The punchline is that many existing libraries do depth-first search
in NFAs (with backtracking).
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Subset Construction}
\begin{textblock}{5}(1,3.5)
\begin{center}
\begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (Q_0) {$\mbox{Q}_0$};
\node[state] (Q_1) [below=of Q_0] {$\mbox{Q}_1$};
\node[state, accepting] (Q_2) [below=of Q_1] {$\mbox{Q}_2$};
\path[->] (Q_0) edge node [left] {\alert{$1$}} (Q_1);
\path[->] (Q_1) edge node [left] {\alert{$0,1$}} (Q_2);
\path[->] (Q_0) edge [loop right] node {\alert{$0,1$}} ();
%\path[->] (Q_1) edge [loop above] node {\alert{$a$}} ();
%\path[->] (Q_2) edge [loop below] node {\alert{$b$}} ();
\end{tikzpicture}
\end{center}
\end{textblock}
\begin{textblock}{11}(6.5,4)
\begin{tabular}{r|cl}
nodes \textcolor{white}{*} & $0$ & $1$\\
\hline
$\{\}$ \textcolor{white}{*} & \onslide<2->{$\{\}$} & \onslide<2->{$\{\}$}\\
\onslide<5->{s:} $\{0\}$ \textcolor{white}{*} & \onslide<3->{$\{0\}$} & \onslide<3->{$\{0,1\}$}\\
$\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{2\}$} & \onslide<3->{$\{2\}$}\\
$\{2\}$ \onslide<5->{*} & \onslide<3->{$\{\}$} & \onslide<3->{$\{\}$}\\
$\{0,1\}$ \textcolor{white}{*} &\onslide<4->{$\{0,2\}$} & \onslide<4->{$\{0,1,2\}$}\\
$\{0,2\}$ \onslide<5->{*} &\onslide<4->{$\{0\}$} & \onslide<4->{$\{0,1\}$}\\
$\{1,2\}$ \onslide<5->{*} & \onslide<4->{$\{2\}$} & \onslide<4->{$\{2\}$}\\
$\{0,1,2\}$ \onslide<5->{*}& \onslide<4->{$\{0,2\}$} & \onslide<4->{$\{0,1,2\}$}\\
\end{tabular}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{The Result}
\footnotesize
\begin{center}
\begin{tikzpicture}[scale=0.5,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20},
baseline=0mm]
\node[state,initial] (q0) {$\{0\}$};
\node[state] (q01) [right=of q0] {$\{0,1\}$};
\node[state,accepting] (q12) [above=of q01] {$\{1,2\}$};
\node[state,accepting] (q02) [below=of q01] {$\{0,2\}$};
\node[state] (q1) [right=2cm of q12] {$\{1\}$};
\node[state,accepting] (q2) [right=2.5cm of q01] {$\{2\}$};
\node[state,accepting] (q012) [right=1.5cm of q02] {$\{0,1,2\}$};
\node[state] (Qn) [right=of q2] {$\{\}$};
\path[->] (q0) edge [loop above] node {\alert{$0$}} ();
\path[->] (q0) edge node [above] {\alert{$1$}} (q01);
\path[->] (q02) edge [bend left] node [left] {\alert{$1$}} (q01);
\path[->] (q02) edge node [below] {\alert{$0$}} (q0);
\path[->] (q01) edge node [above] {\alert{$1$}} (q012);
\path[->] (q01) edge [bend left] node [right] {\alert{$0$}} (q02);
\path[->] (q12) edge node [below] {\alert{$0,1$}} (q2);
\path[->] (q1) edge node [right] {\alert{$0,1$}} (q2);
\path[->] (q2) edge node [above] {\alert{$0,1$}} (Qn);
\path[->] (q012) edge [loop right] node {\alert{$1$}} ();
\path[->] (q012) edge node [below] {\alert{$0$}} (q02);
\path[->] (Qn) edge [loop above] node {$\alert{0},\alert{1}$} ();
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Removing Dead States}
\footnotesize
\begin{center}
\begin{tabular}{ll}
\large DFA: & \large (original) NFA:\\
\raisebox{0mm}{%
\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20}]
\node[state,initial] (q0) {$\{0\}$};
\node[state] (q01) [right=of q0] {$\{0,1\}$};
\node[state,accepting] (q02) [below=of q01] {$\{0,2\}$};
\node[state,accepting] (q012) [right=1.5cm of q02] {$\{0,1,2\}$};
\path[->] (q0) edge [loop above] node {\alert{$0$}} ();
\path[->] (q0) edge node [above] {\alert{$1$}} (q01);
\path[->] (q02) edge [bend left] node [left] {\alert{$1$}} (q01);
\path[->] (q02) edge node [below] {\alert{$0$}} (q0);
\path[->] (q01) edge node [above] {\alert{$1$}} (q012);
\path[->] (q01) edge [bend left] node [right] {\alert{$0$}} (q02);
\path[->] (q012) edge [loop right] node {\alert{$1$}} ();
\path[->] (q012) edge node [below] {\alert{$0$}} (q02);
\end{tikzpicture}}
&
\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (Q_0) {$\mbox{Q}_0$};
\node[state] (Q_1) [below=of Q_0] {$\mbox{Q}_1$};
\node[state, accepting] (Q_2) [below=of Q_1] {$\mbox{Q}_2$};
\path[->] (Q_0) edge node [left] {\alert{$1$}} (Q_1);
\path[->] (Q_1) edge node [left] {\alert{$0,1$}} (Q_2);
\path[->] (Q_0) edge [loop right] node {\alert{$0,1$}} ();
\end{tikzpicture}
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Subset Construction ($\epsilon$NFA)}
\begin{textblock}{5}(1,1.5)
\begin{center}
\begin{tikzpicture}[node distance=6mm,scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (Q_0) {$\mbox{Q}_0$};
\node[state] (Q_1) [above=of Q_0] {$\mbox{Q}_1$};
\node[state, accepting] (Q_2) [below=of Q_0] {$\mbox{Q}_2$};
\path[->] (Q_0) edge node [left] {\alert{$\epsilon$}} (Q_1);
\path[->] (Q_0) edge node [left] {\alert{$\epsilon$}} (Q_2);
\path[->] (Q_0) edge [loop right] node {\alert{$a$}} ();
\path[->] (Q_1) edge [loop above] node {\alert{$a$}} ();
\path[->] (Q_2) edge [loop below] node {\alert{$b$}} ();
\end{tikzpicture}
\end{center}
\end{textblock}
\begin{textblock}{11}(6.5,4.5)
\begin{tabular}{r|cl}
nodes \textcolor{white}{*} & $a$ & $b$\\
\hline
$\{\}$ \textcolor{white}{*} & \onslide<2->{$\{\}$} & \onslide<2->{$\{\}$}\\
$\{0\}$ \textcolor{white}{*} & \onslide<3->{$\{0,1,2\}$} & \onslide<3->{$\{2\}$}\\
$\{1\}$ \textcolor{white}{*} & \onslide<3->{$\{1\}$} & \onslide<3->{$\{\}$}\\
$\{2\}$ \onslide<5->{*} & \onslide<3->{$\{\}$} & \onslide<3->{$\{2\}$}\\
$\{0,1\}$ \textcolor{white}{*} &\onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
$\{0,2\}$ \onslide<5->{*} &\onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
$\{1,2\}$ \onslide<5->{*} & \onslide<4->{$\{1\}$} & \onslide<4->{$\{2\}$}\\
\onslide<5->{s:} $\{0,1,2\}$ \onslide<5->{*}& \onslide<4->{$\{0,1,2\}$} & \onslide<4->{$\{2\}$}\\
\end{tabular}
\end{textblock}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{The Result}
\footnotesize
\begin{center}
\begin{tikzpicture}[scale=0.5,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20},
baseline=0mm]
\node[state,initial,accepting] (q012) {$\{0,1,2\}$};
\node[state,accepting] (q02) [right=of q012] {$\{0,2\}$};
\node[state] (q01) [above=of q02] {$\{0,1\}$};
\node[state,accepting] (q12) [below=of q02] {$\{1,2\}$};
\node[state] (q0) [right=2cm of q01] {$\{0\}$};
\node[state] (q1) [right=2.5cm of q02] {$\{1\}$};
\node[state,accepting] (q2) [right=1.5cm of q12] {$\{2\}$};
\node[state] (qn) [right=of q1] {$\{\}$};
\path[->] (q012) edge [loop below] node {\alert{$a$}} ();
\path[->] (q012) edge node [above] {\alert{$b$}} (q2);
\path[->] (q12) edge [bend left] node [below,pos=0.4] {\alert{$a$}} (q1);
\path[->] (q12) edge node [below] {\alert{$b$}} (q2);
\path[->] (q02) edge node [above] {\alert{$a$}} (q012);
\path[->] (q02) edge [bend left] node [above, pos=0.8] {\alert{$b$}} (q2);
\path[->] (q01) edge node [below] {\alert{$a$}} (q012);
\path[->] (q01) edge [bend left] node [above] {\alert{$b$}} (q2);
\path[->] (q0) edge node [below] {\alert{$a$}} (q012);
\path[->] (q0) edge node [right, pos=0.2] {\alert{$b$}} (q2);
\path[->] (q1) edge [loop above] node {\alert{$a$}} ();
\path[->] (q1) edge node [above] {\alert{$b$}} (qn);
\path[->] (q2) edge [loop right] node {\alert{$b$}} ();
\path[->] (q2) edge node [below] {\alert{$a$}} (qn);
\path[->] (qn) edge [loop above] node {$\alert{a},\alert{b}$} ();
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Removing Dead States}
\footnotesize
\begin{center}
\begin{tabular}{ll}
DFA: & (original) NFA:\\
\raisebox{10mm}{%
\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20}]
\node[state,initial,accepting] (q012) {$\{0,1,2\}$};
\node[state,accepting] (q2) [right=of q012] {$\{2\}$};
\node[state] (qn) [right=of q2] {$\{\}$};
\path[->] (q012) edge [loop below] node {\alert{$a$}} ();
\path[->] (q012) edge node [above] {\alert{$b$}} (q2);
\path[->] (q2) edge [loop below] node {\alert{$b$}} ();
\path[->] (q2) edge node [below] {\alert{$a$}} (qn);
\path[->] (qn) edge [loop above] node
{$\alert{a},\alert{b}$} ();
\end{tikzpicture}}
&
\begin{tikzpicture}[scale=0.7,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20},]
\node[state,initial] (Q_0) {$\mbox{Q}_0$};
\node[state] (Q_1) [above=of Q_0] {$\mbox{Q}_1$};
\node[state, accepting] (Q_2) [below=of Q_0] {$\mbox{Q}_2$};
\path[->] (Q_0) edge node [left] {\alert{$\epsilon$}} (Q_1);
\path[->] (Q_0) edge node [left] {\alert{$\epsilon$}} (Q_2);
\path[->] (Q_0) edge [loop right] node {\alert{$a$}} ();
\path[->] (Q_1) edge [loop above] node {\alert{$a$}} ();
\path[->] (Q_2) edge [loop below] node {\alert{$b$}} ();
\end{tikzpicture}
\end{tabular}
\end{center}
\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<2->{\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<2->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}
\end{tikzpicture}\\
\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 in at least one case, 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{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) {$\mbox{Q}_0$};
\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};
\path[->] (Q_0) edge node [above] {\alert{$a$}} (Q_1);
\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_4);
\path[->] (Q_4) edge [loop right] node {\alert{$a, b$}} ();
\path[->] (Q_3) edge node [right] {\alert{$a$}} (Q_4);
\path[->] (Q_2) edge node [above] {\alert{$a$}} (Q_3);
\path[->] (Q_1) edge node [right] {\alert{$b$}} (Q_2);
\path[->] (Q_0) edge node [above] {\alert{$b$}} (Q_2);
\path[->] (Q_2) edge [loop left] node {\alert{$b$}} ();
\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0);
\end{tikzpicture}
\end{center}
\mbox{}\\[-20mm]\mbox{}
\begin{center}
\begin{tikzpicture}[scale=0.8,line width=0.8mm]
\draw (0,0) -- (4,0);
\draw (0,1) -- (4,1);
\draw (0,2) -- (3,2);
\draw (0,3) -- (2,3);
\draw (0,4) -- (1,4);
\draw (0,0) -- (0, 4);
\draw (1,0) -- (1, 4);
\draw (2,0) -- (2, 3);
\draw (3,0) -- (3, 2);
\draw (4,0) -- (4, 1);
\draw (0.5,-0.5) node {$\mbox{Q}_0$};
\draw (1.5,-0.5) node {$\mbox{Q}_1$};
\draw (2.5,-0.5) node {$\mbox{Q}_2$};
\draw (3.5,-0.5) node {$\mbox{Q}_3$};
\draw (-0.5, 3.5) node {$\mbox{Q}_1$};
\draw (-0.5, 2.5) node {$\mbox{Q}_2$};
\draw (-0.5, 1.5) node {$\mbox{Q}_3$};
\draw (-0.5, 0.5) node {$\mbox{Q}_4$};
\draw (0.5,0.5) node {\large$\star$};
\draw (1.5,0.5) node {\large$\star$};
\draw (2.5,0.5) node {\large$\star$};
\draw (3.5,0.5) node {\large$\star$};
\end{tikzpicture}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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) {$\mbox{Q}_0$};
\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{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 {$\mbox{Q}_0$};
\draw (1.5,-0.5) node {$\mbox{Q}_1$};
\draw (2.5,-0.5) node {$\mbox{Q}_2$};
\draw (3.5,-0.5) node {$\mbox{Q}_3$};
\draw (-0.5, 3.5) node {$\mbox{Q}_1$};
\draw (-0.5, 2.5) node {$\mbox{Q}_2$};
\draw (-0.5, 1.5) node {$\mbox{Q}_3$};
\draw (-0.5, 0.5) node {$\mbox{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) {$\mbox{Q}_{0, 2}$};
\node[state] (Q_13) [right=of Q_02] {$\mbox{Q}_{1, 3}$};
\node[state, accepting] (Q_4) [right=of Q_13] {$\mbox{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{Alternatives}
\mbox{}\\[-14mm]\mbox{}
\begin{center}
\begin{tikzpicture}[>=stealth',very thick,auto,
every state/.style={minimum size=0pt,
inner sep=2pt,draw=blue!50,very thick,fill=blue!20}]
\only<1>{\node[state,initial] (Q_0) {$\mbox{Q}_0$};}
\only<2->{\node[state,accepting] (Q_0) {$\mbox{Q}_0$};}
\node[state] (Q_1) [right=of Q_0] {$\mbox{Q}_1$};
\node[state] (Q_2) [below right=of Q_0] {$\mbox{Q}_2$};
\node[state] (Q_3) [right=of Q_2] {$\mbox{Q}_3$};
\only<1>{\node[state, accepting] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
\only<2->{\node[state, initial right] (Q_4) [right=of Q_1] {$\mbox{Q}_4$};}
\only<1-2>{
\path[->] (Q_0) edge node [above] {\alert{$a$}} (Q_1);
\path[->] (Q_1) edge node [above] {\alert{$a$}} (Q_4);
\path[->] (Q_4) edge [loop above] node {\alert{$a, b$}} ();
\path[->] (Q_3) edge node [right] {\alert{$a$}} (Q_4);
\path[->] (Q_2) edge node [above] {\alert{$a$}} (Q_3);
\path[->] (Q_1) edge node [right] {\alert{$b$}} (Q_2);
\path[->] (Q_0) edge node [above] {\alert{$b$}} (Q_2);
\path[->] (Q_2) edge [loop left] node {\alert{$b$}} ();
\path[->] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0);}
\only<3->{
\path[<-] (Q_0) edge node [above] {\alert{$a$}} (Q_1);
\path[<-] (Q_1) edge node [above] {\alert{$a$}} (Q_4);
\path[<-] (Q_4) edge [loop above] node {\alert{$a, b$}} ();
\path[<-] (Q_3) edge node [right] {\alert{$a$}} (Q_4);
\path[<-] (Q_2) edge node [above] {\alert{$a$}} (Q_3);
\path[<-] (Q_1) edge node [right] {\alert{$b$}} (Q_2);
\path[<-] (Q_0) edge node [above] {\alert{$b$}} (Q_2);
\path[<-] (Q_2) edge [loop left] node {\alert{$b$}} ();
\path[<-] (Q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (Q_0);}
\end{tikzpicture}
\end{center}
\mbox{}\\[-18mm]
\small
\begin{itemize}
\item<1-> exchange initial / accepting states\\[-2mm]
\item<2-> reverse all edges\\[-2mm]
\item<3-> subset construction $\Rightarrow$ DFA\\[-2mm]
\item<4-> remove dead states\\[-2mm]
\item<5-> repeat once more
\onslide<6->{$\Rightarrow$ minimal DFA}
\end{itemize}
\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<1->{\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<1->{\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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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) {$\mbox{Q}_0$};}
\only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}
\only<1>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
\only<2->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
\only<1>{\node[state, accepting] (q2) at ( 2,1) {$\mbox{Q}_2$};}
\only<2->{\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}
\onslide<3>{How to get from a DFA to a regular expression?}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}
\only<1->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
\only<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}\pause\bigskip
\onslide<2->{
You know how to solve since school days, no?
\begin{center}
\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$2\, \mbox{Q}_0 + 3 \,\mbox{Q}_1 + 4\, \mbox{Q}_2$}\\
\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$2 \,\mbox{Q}_0 + 3\, \mbox{Q}_1 + 1\, \mbox{Q}_2$}\\
\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$1\, \mbox{Q}_0 + 5\, \mbox{Q}_1 + 2\, \mbox{Q}_2$}\\
\end{tabular}
\end{center}
}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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) {$\mbox{Q}_0$};}
\only<1->{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
\only<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
\onslide<2->{
\begin{center}
\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b + \ONE$}\\
\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}
}
\only<3-9>{\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{$\mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b + \ONE$}\\
\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
\end{tabular}
\end{bubble}
\end{textblock}}
\only<4-9>{\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{$\mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b + \ONE$}\\
\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
\end{tabular}
\end{bubble}
\end{textblock}}
\only<6-9>{\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{$\mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b + \ONE$}\\
\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}
\end{tabular}
\end{bubble}
\end{textblock}}
\only<7-9>{\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{$\mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b) + \ONE$}\\
\end{tabular}
\end{bubble}
\end{textblock}}
\only<8-9>{\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<9-10>{\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}}
\only<5-6>{
\begin{textblock}{6}(0.7,11.9)
\begin{bubble}[6.7cm]
Arden's Lemma:
\begin{center}
If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
\end{center}
\end{bubble}
\end{textblock}}
\only<8>{
\begin{textblock}{6}(1.1,7.8)
\begin{bubble}[6.7cm]
Arden's Lemma:
\begin{center}
If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
\end{center}
\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}};
\onslide<1->{\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<1->{\path[->, red, line width=2mm] (dfa) edge node [below=9mm, black] {minimisation} (mdfa);}
\onslide<1->{\path[->, red, line width=2mm] (dfa) edge [bend left=45] (rexp);}
\end{tikzpicture}\\
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{Regular Languages (3)}
A language is \alert{\bf regular} iff there exists a regular
expression that recognises all its strings.\bigskip\medskip
or {\bf equivalently}\bigskip\medskip
A language is \alert{\bf regular} iff there exists a
deterministic finite automaton that recognises all its
strings.\bigskip\medskip\pause
Why is every finite set of strings a regular language?
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\begin{frame}[c]
%
%Given the function
%
%\begin{center}
%\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
%$rev(\ZERO)$ & $\dn$ & $\ZERO$\\
%$rev(\ONE)$ & $\dn$ & $\ONE$\\
%$rev(c)$ & $\dn$ & $c$\\
%$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
%$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
%$rev(r^*)$ & $\dn$ & $rev(r)^*$\\
%\end{tabular}}
%\end{center}
%
%
%and the set
%
%\begin{center}
%\bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$}
%\end{center}
%
%prove whether
%
%\begin{center}
%\bl{$L(rev(r)) = Rev (L(r))$}
%\end{center}
%
%\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}[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}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{
\setbeamercolor{background canvas}{bg=cream}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
\frametitle{\boldmath{}$(a^*)^* \cdot b$}
\begin{center}
\begin{tikzpicture}
\begin{axis}[
xlabel={\pcode{a}s},
%%x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,15,...,30},
xmax=33,
ymax=35,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
width=9cm,
height=6cm,
legend entries={Java 8,Python,JavaScript,Swift,Dart},
legend pos=outer north east,
legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
%\addplot[red,mark=triangle*, mark options={fill=red}] table {nfadepth2.data};
\end{axis}
\end{tikzpicture}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}<1-3>[c]
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
{
\setbeamercolor{background canvas}{bg=cream}
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[scale=1.5,>=stealth',very thick,
every state/.style={minimum size=0pt,
draw=blue!50,very thick,fill=blue!20}]
\node[state,initial] (q0) at (0,2) {$q_0$};
\node[state,accepting] (q1) at (2,2) {$q_1$};
\node[state] (q2) at (0,0) {$q_2$};
\node[state] (q3) at (2,0) {$q_3$};
\path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
(q1) edge[bend left] node[above] {\alert{$a$}} (q0)
(q2) edge[bend left] node[above] {\alert{$a$}} (q3)
(q3) edge[bend left] node[above] {\alert{$a$}} (q2)
(q0) edge[bend left] node[right] {\alert{$b$}} (q2)
(q2) edge[bend left] node[left] {\alert{$b$}} (q0)
(q1) edge[bend left] node[right] {\alert{$b$}} (q3)
(q3) edge[bend left] node[left] {\alert{$b$}} (q1);
\end{tikzpicture}
\end{center}
\hfill{}Which language?
\end{frame}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}<1-15>[c]
\end{frame}
\begin{frame}[t]
\begin{mybox3}{}
I always thought dfa's needed a transition for each state for each
character, and if not it would be an nfa not a dfa. Is there an
example that disproves this?
\end{mybox3}
\end{frame}
\begin{frame}<1-12>[c]
\end{frame}
\begin{frame}[t]
\begin{mybox3}{}
Do the regular expression matchers in Python and Java 8 have more
features than the one implemented in this module? Or is there
another reason for their inefficiency?
\end{mybox3}
\end{frame}
\begin{frame}[c]
\begin{itemize}
\item CW / censored some msgs
\item power law / proof
\item CW feedback
\item too polished CW submissions
\item no open book
\end{itemize}
\end{frame}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: