\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$};