\documentclass[dvipsnames,14pt,t]{beamer}
\usepackage{beamerthemeplaincu}
%%%\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{mathpartir}
\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{plotmarks}
\usetikzlibrary{backgrounds}
\usepackage{graphicx}
\definecolor{javared}{rgb}{0.6,0,0} % for strings
\definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments
\definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords
\definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc
\makeatletter
\lst@CCPutMacro\lst@ProcessOther {"2D}{\lst@ttfamily{-{}}{-{}}}
\@empty\z@\@empty
\makeatother
\lstset{language=Java,
basicstyle=\consolas,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
morecomment=[s][\color{javadocblue}]{/**}{*/},
numbers=left,
numberstyle=\tiny\color{black},
stepnumber=1,
numbersep=10pt,
tabsize=2,
showspaces=false,
showstringspaces=false}
\lstdefinelanguage{scala}{
morekeywords={abstract,case,catch,class,def,%
do,else,extends,false,final,finally,%
for,if,implicit,import,match,mixin,%
new,null,object,override,package,%
private,protected,requires,return,sealed,%
super,this,throw,trait,true,try,%
type,val,var,while,with,yield},
otherkeywords={=>,<-,<\%,<:,>:,\#,@,->},
sensitive=true,
morecomment=[l]{//},
morecomment=[n]{/*}{*/},
morestring=[b]",
morestring=[b]',
morestring=[b]"""
}
\lstset{language=Scala,
basicstyle=\consolas,
keywordstyle=\color{javapurple}\bfseries,
stringstyle=\color{javagreen},
commentstyle=\color{javagreen},
morecomment=[s][\color{javadocblue}]{/**}{*/},
numbers=left,
numberstyle=\tiny\color{black},
stepnumber=1,
numbersep=10pt,
tabsize=2,
showspaces=false,
showstringspaces=false}
% beamer stuff
\renewcommand{\slidecaption}{AFL 04, King's College London, 16.~October 2013}
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions
% The data files, written on the first run.
\begin{filecontents}{re-python.data}
1 0.029
5 0.029
10 0.029
15 0.032
16 0.042
17 0.042
18 0.055
19 0.084
20 0.136
21 0.248
22 0.464
23 0.899
24 1.773
25 3.505
26 6.993
27 14.503
28 29.307
#29 58.886
\end{filecontents}
\begin{filecontents}{re-ruby.data}
1 0.00006
2 0.00003
3 0.00001
4 0.00001
5 0.00001
6 0.00002
7 0.00002
8 0.00004
9 0.00007
10 0.00013
11 0.00026
12 0.00055
13 0.00106
14 0.00196
15 0.00378
16 0.00764
17 0.01606
18 0.03094
19 0.06508
20 0.12420
21 0.25393
22 0.51449
23 1.02174
24 2.05998
25 4.22514
26 8.42479
27 16.88678
28 34.79653
\end{filecontents}
\begin{filecontents}{nfa.data}
0 0.00099
5 0.01304
10 0.05350
15 0.10152
20 0.10876
25 0.06984
30 0.09693
35 0.04805
40 0.07512
45 0.07624
50 0.10451
55 0.13285
60 0.15748
65 0.19982
70 0.24075
75 0.28963
80 0.35734
85 0.43735
90 0.49692
95 0.59551
100 0.72236
\end{filecontents}
\begin{filecontents}{nfasearch.data}
0 0.00009
1 0.00147
2 0.00030
3 0.00062
4 0.00132
5 0.00177
6 0.00487
7 0.00947
8 0.01757
9 0.02050
10 0.02091
11 0.04002
12 0.08662
13 0.17269
14 0.37255
15 0.81935
16 1.76254
17 3.89442
18 8.42263
19 17.89661
20 38.21481
\end{filecontents}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}<1>[t]
\frametitle{%
\begin{tabular}{@ {}c@ {}}
\\[-3mm]
\LARGE Automata and \\[-2mm]
\LARGE Formal Languages (4)\\[3mm]
\end{tabular}}
\normalsize
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
Office: & S1.27 (1st floor Strand Building)\\
Slides: & KEATS (also home work is there)\\
\end{tabular}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\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>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}DFAs\end{tabular}}
A deterministic finite automaton consists of:
\begin{itemize}
\item a finite set of states, \bl{$Q$}
\item one of these states is the start state, \bl{$q_0$}
\item there is transition function, \bl{$\delta$}, and
\item some states are accepting states, \bl{$F$}
\medskip
\end{itemize}
\begin{center}
\bl{$A(Q, q_0, \delta, F)$}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}State Nodes\end{tabular}}
\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont
\lstinputlisting{../progs/appA.scala}}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}DFAs\;\;\;\end{tabular}}
\mbox{}\\[7mm]
\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont
\lstinputlisting{../progs/appB.scala}}}
\only<2->{
\begin{textblock}{9}(7.5,0.5)
\begin{tikzpicture}
\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
{\normalsize\color{darkgray}
\begin{minipage}{6cm}
\begin{tabular}{l}
\bl{$\hat{\delta}(q, \texttt{""}) \dn q$}\\
\bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\[4mm]
\bl{$\hat{\delta}(q_0, s) \in F$}
\end{tabular}
\end{minipage}};
\end{tikzpicture}
\end{textblock}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\mbox{}\hspace{-10mm}
\begin{tikzpicture}[scale=0.6,>=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}
\only<1->{
\begin{textblock}{9}(7.4,3.5)
\begin{tikzpicture}
\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
{\normalsize\color{darkgray}
\begin{minipage}{6.6cm}
\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont
\lstinputlisting{../progs/appC.scala}}}
\end{minipage}};
\end{tikzpicture}
\end{textblock}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}NFAs\end{tabular}}
A non-deterministic finite automaton \bl{$A(Q, q_0, \delta, F)$} consists of:\medskip
\begin{itemize}
\item a finite set of states, \bl{$Q$}
\item one of these states is the start state, \bl{$q_0$}
\item some states are accepting states, \bl{$F$},
\item there is transition \alert{relation}, \bl{$\delta$}, and
\item there are \alert{silent} transitions\medskip
\end{itemize}
\begin{center}
\begin{tabular}{c}
\bl{$(q_1, a) \rightarrow q_2$}\\
\bl{$(q_1, a) \rightarrow q_3$}\\
\end{tabular}
\hspace{10mm}
\begin{tabular}{c}
\bl{$(q_1, \epsilon) \rightarrow q_2$}\\
\end{tabular}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont
\lstinputlisting{../progs/appD.scala}}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\mbox{}\hspace{-10mm}
\begin{tikzpicture}[scale=0.6,>=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) [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}
\only<1->{
\begin{textblock}{9}(6,1.5)
\begin{tikzpicture}
\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
{\normalsize\color{darkgray}
\begin{minipage}{7cm}
\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont
\lstinputlisting{../progs/appE.scala}}}
\end{minipage}};
\end{tikzpicture}
\end{textblock}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Rexp to NFA}
Thompson's construction of a NFA from a regular expression:
\begin{center}
\begin{tabular}[t]{l@{\hspace{10mm}}l}
\raisebox{1mm}{\bl{$\varnothing$}} &
\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{$\epsilon$}} &
\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{2mm}{\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{Case $r_1\cdot r_2$}
\mbox{}\bigskip
\onslide<1>{By recursion we are given two automata:\bigskip}
{\centering\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 (r_1) [right=of q_0] {$\ldots$};
\only<1>{
\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{}$};}
\only<2>{
\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{}$};}
\only<1>{\node[state, initial] (a_0) [right=2.5cm of t_1] {$\mbox{}$};}
\only<2>{\node[state] (a_0) [right=2.5cm of t_1] {$\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{}$};
\only<2>{
\path[->] (t_1) edge node [above, pos=0.3] {\alert{$\epsilon$}} (a_0);
\path[->] (t_2) edge node [above] {\alert{$\epsilon$}} (a_0);
\path[->] (t_3) edge node [below] {\alert{$\epsilon$}} (a_0);
}
\begin{pgfonlayer}{background}
\only<1>{\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)] {};}
\only<1>{\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)] {};}
\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};}
\only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};}
\only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};}
\only<2>{\node [yshift=2mm] at (3.north) {\bl{$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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{Case $r_1+ r_2$}
\onslide<1>{By recursion we are given two automata:\smallskip}
\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\onslide<1>{\node at (0,0) (1) {$\mbox{}$};}
\onslide<2>{\node at (0,0) [state, initial] (1) {$\mbox{}$};}
\only<1>{
\node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$};
\node[state, initial] (3) [below right=16mm of 1] {$\mbox{}$};}
\only<2>{
\node[state] (2) [above right=16mm of 1] {$\mbox{}$};
\node[state] (3) [below right=16mm of 1] {$\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{}$};
\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{}$};
\only<2>{
\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2);
\path[->] (1) edge node [below] {\alert{$\epsilon$}} (3);
}
\begin{pgfonlayer}{background}
\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
\only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};}
\only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};}
\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};}
\only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};}
\only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};}
\end{pgfonlayer}
\end{tikzpicture}
\small
We (1) need to introduce a new starting state and (2) connect it to the original two starting states.
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Case $r^*$}
\onslide<1>{By recursion we are given an automaton for $r$:\smallskip}
\hspace{2cm}\begin{tikzpicture}[node distance=3mm,
>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},]
\onslide<1>{\node at (0,0) (1) {$\mbox{}$};}
\onslide<2->{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};}
\only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};}
\only<2->{\node[state] (2) [right=16mm of 1] {$\mbox{}$};}
\node (a) [right=of 2] {$\ldots$};
\only<1>{
\node[state, accepting] (a1) [right=of a] {$\mbox{}$};
\node[state, accepting] (a2) [above=of a1] {$\mbox{}$};
\node[state, accepting] (a3) [below=of a1] {$\mbox{}$};}
\only<2->{
\node[state] (a1) [right=of a] {$\mbox{}$};
\node[state] (a2) [above=of a1] {$\mbox{}$};
\node[state] (a3) [below=of a1] {$\mbox{}$};}
\only<2->{
\path[->] (1) edge node [above] {\alert{$\epsilon$}} (2);
\path[->] (a1) edge [bend left=45] node [above] {\alert{$\epsilon$}} (1);
\path[->] (a2) edge [bend right] node [below] {\alert{$\epsilon$}} (1);
\path[->] (a3) edge [bend left=45] node [below] {\alert{$\epsilon$}} (1);
}
\begin{pgfonlayer}{background}
\only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};}
\only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};}
\only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};}
\only<2->{\node [yshift=3mm] at (2.north) {\bl{$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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
\mbox{}\\[-13mm]
\begin{tikzpicture}[y=.2cm, x=.09cm]
%axis
\draw (0,0) -- coordinate (x axis mid) (100,0);
\draw (0,0) -- coordinate (y axis mid) (0,30);
%ticks
\foreach \x in {0,10,...,100}
\draw (\x,1pt) -- (\x,-3pt)
node[anchor=north] {\x};
\foreach \y in {0,5,...,30}
\draw (1pt,\y) -- (-3pt,\y)
node[anchor=east] {\y};
%labels
\node[below=0.6cm] at (x axis mid) {\bl{a}s};
\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
%plots
\draw[color=blue] plot[mark=*, mark options={fill=white}]
file {re-python.data};
\draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
file {nfa.data};
\draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
file {re-ruby.data};
%legend
\begin{scope}[shift={(4,20)}]
\draw[color=blue] (0,0) --
plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0)
node[right]{\small Python};
\draw[yshift=-\baselineskip, color=brown] (0,0) --
plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
node[right]{\small Ruby};
\draw[yshift=\baselineskip, color=red] (0,0) --
plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
node[right]{\small NFA 1};
\end{scope}
\end{tikzpicture}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{Greedy Depth-First}
\hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont
\lstinputlisting{../progs/appG.scala}}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
\mbox{}\\[-13mm]
\begin{tikzpicture}[y=.2cm, x=.3cm]
%axis
\draw (0,0) -- coordinate (x axis mid) (30,0);
\draw (0,0) -- coordinate (y axis mid) (0,30);
%ticks
\foreach \x in {0,5,...,30}
\draw (\x,1pt) -- (\x,-3pt)
node[anchor=north] {\x};
\foreach \y in {0,5,...,30}
\draw (1pt,\y) -- (-3pt,\y)
node[anchor=east] {\y};
%labels
\node[below=0.6cm] at (x axis mid) {\bl{a}s};
\node[rotate=90, left=1.2cm] at (y axis mid) {secs};
%plots
\draw[color=blue] plot[mark=*, mark options={fill=white}]
file {re-python.data};
\draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
file {nfasearch.data};
\draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
file {re-ruby.data};
%legend
\begin{scope}[shift={(4,20)}]
\draw[color=blue] (0,0) --
plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0)
node[right]{\small Python};
\draw[yshift=-\baselineskip, color=brown] (0,0) --
plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
node[right]{\small Ruby};
\draw[yshift=\baselineskip, color=red] (0,0) --
plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)
node[right]{\small NFA 2};
\end{scope}
\end{tikzpicture}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}<2>[c]
\frametitle{DFA to Rexp}
\begin{center}
\begin{tikzpicture}[scale=2, line width=0.5mm]
\only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
\only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};}
\only<1>{\node[state] (q1) at ( 1,1) {$q_1$};}
\only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};}
\only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};}
\only<2->{\node[state] (q2) at ( 2,1) {$q_2$};}
\path[->] (q0) edge[bend left] node[above] {$a$} (q1)
(q1) edge[bend left] node[above] {$b$} (q0)
(q2) edge[bend left=50] node[below] {$b$} (q0)
(q1) edge node[above] {$a$} (q2)
(q2) edge [loop right] node {$a$} ()
(q0) edge [loop below] node {$b$} ()
;
\end{tikzpicture}
\end{center}
\onslide<3>{How to get from a DFA to a regular expression?}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[scale=2, line width=0.5mm]
\only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
\only<1->{\node[state] (q1) at ( 1,1) {$q_1$};}
\only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
\path[->] (q0) edge[bend left] node[above] {$a$} (q1)
(q1) edge[bend left] node[above] {$b$} (q0)
(q2) edge[bend left=50] node[below] {$b$} (q0)
(q1) edge node[above] {$a$} (q2)
(q2) edge [loop right] node {$a$} ()
(q0) edge [loop below] node {$b$} ()
;
\end{tikzpicture}
\end{center}\pause\bigskip
\onslide<2->{
\begin{center}
\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
\bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\
\bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\
\bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\
\end{tabular}
\end{center}
}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\begin{center}
\begin{tikzpicture}[scale=2, line width=0.5mm]
\only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};}
\only<1->{\node[state] (q1) at ( 1,1) {$q_1$};}
\only<1->{\node[state] (q2) at ( 2,1) {$q_2$};}
\path[->] (q0) edge[bend left] node[above] {$a$} (q1)
(q1) edge[bend left] node[above] {$b$} (q0)
(q2) edge[bend left=50] node[below] {$b$} (q0)
(q1) edge node[above] {$a$} (q2)
(q2) edge [loop right] node {$a$} ()
(q0) edge [loop below] node {$b$} ()
;
\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]
\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$} tests wether
\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 chance.
\item All unmarked pairs can be merged.
\end{enumerate}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}<1-2>[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);
\end{tikzpicture}
\end{center}\pause
\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\begin{itemize}
\item Assuming you have the alphabet \bl{$\{a, b, c\}$}\bigskip
\item Give a regular expression that can recognise all strings that have at least one \bl{$b$}.
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: