\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{plotmarks}

\usetikzlibrary{calc}

\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 02, King's College London, 2.~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{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}<1>[t]

\frametitle{%

  \begin{tabular}{@ {}c@ {}}

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

  \LARGE Formal Languages (2)\\[3mm] 

  \end{tabular}}

  %\begin{center}

  %\includegraphics[scale=0.3]{pics/ante1.jpg}\hspace{5mm}

  %\includegraphics[scale=0.31]{pics/ante2.jpg}\\

  %\footnotesize\textcolor{gray}{Antikythera automaton, 100 BC (Archimedes?)}

  %\end{center}

\normalsize

  \begin{center}

  \begin{tabular}{ll}

  Email:  & christian.urban at kcl.ac.uk\\

  Office: & S1.27 (1st floor Strand Building)\\

  Slides: & KEATS 

  \end{tabular}

  \end{center}

\end{frame}}

 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Languages\end{tabular}}

A \alert{language} is a set of strings.\bigskip

A \alert{regular expression} specifies a set of strings, or language.

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[t]

\frametitle{\begin{tabular}{c}Strings\end{tabular}}

Different ways of writing strings:

\begin{center}

\begin{tabular}{ccc}

\bl{\consolas"$hello$"}\quad{} &  \bl{$[h, e, l, l, o]$} & \quad\bl{$h\!::\!e\!::\!l\!::\!l\!::\!o\!::\!N\!il$}\bigskip\\

\bl{\consolas ""}       &       \bl{$[]$}                & \bl{$N$\!$il$}

\end{tabular}

\end{center}\pause

The concatenation operation on strings and sets of strings:

\begin{center}

\begin{tabular}{l}

\bl{{\consolas"$f\!oo$"}$\;@\;${\consolas"$bar$"}$\;=\;${\consolas"$f\!oobar$"}}\medskip\\

\bl{$A \;@\; B \dn \{ s_1 @ s_2 \mid s_1 \in A \wedge s_2 \in B\}$}

\end{tabular}

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[t]

\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}

Their inductive definition:

\begin{textblock}{6}(2,6.5)

  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}

  \bl{r} & \bl{$::=$}  & \bl{$\varnothing$}  & null\\

         & \bl{$\mid$} & \bl{$\epsilon$}        & empty string / {\consolas""} / $[]$\\

         & \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{textblock}

\only<2->{

\begin{textblock}{9}(4,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}{9cm}

\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont

\texttt{\lstinputlisting{../progs/app51.scala}}}}

\end{minipage}};

\end{tikzpicture}

\end{textblock}}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}}

\begin{textblock}{15}(1,4)

 \begin{tabular}{@ {}rcl}

 \bl{$L(\varnothing)$}     & \bl{$\dn$} & \bl{$\varnothing$}\\

 \bl{$L(\epsilon)$}          & \bl{$\dn$} & \bl{$\{$""$\}$}\\

 \bl{$L(c)$}                     & \bl{$\dn$} & \bl{$\{"c"\}$}\\

 \bl{$L(r_1 + r_2)$}        & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\

 \bl{$L(r_1 \cdot r_2)$}  & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\

 \bl{$L(r^*)$}                   & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0} L(r)^n$}\\

  \end{tabular}\bigskip

\only<2->{  

\hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{""\}$}\\

\textcolor{blue}{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}}  

\end{textblock}

\only<1->{

\begin{textblock}{6}(9,12)\small

\bl{$L$} is a function from regular expressions to sets of strings\\

\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}

\end{textblock}}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\large

\begin{center}

What is \bl{$L(a^*)$}?

\end{center}  

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

\newcommand{\YES}{\textcolor{gray}{yes}}

\newcommand{\NO}{\textcolor{gray}{no}}

\newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}}

\begin{center}

\begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l}

&\bl{$(a + b)  + c$} & \bl{$\equiv^?$} & \bl{$a + (b + c)$} & \onslide<2->{\YES}\\

&\bl{$a + a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<3->{\YES}\\

&\bl{$(a \cdot b)  \cdot c$} & \bl{$\equiv^?$} & \bl{$a \cdot (b \cdot c)$} & \onslide<4->{\YES}\\

&\bl{$a \cdot a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<5->{\NO}\\

&\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\

&\bl{$\varnothing^*$} & \bl{$\equiv^?$} & \bl{$\varnothing$} & \onslide<7->{\NO}\\

\FORALLR &\bl{$r \cdot \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<8->{\YES}\\

\FORALLR &\bl{$r + \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<9->{\NO}\\

\FORALLR &\bl{$r + \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<10->{\YES}\\

\FORALLR &\bl{$r \cdot \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<11->{\NO}\\

&\bl{$c \cdot (a + b)$} & \bl{$\equiv^?$} & \bl{$(c \cdot a) + (c \cdot b)$} & \onslide<12->{\YES}\\

&\bl{$a^*$} & \bl{$\equiv^?$} & \bl{$\epsilon + (a \cdot a^*)$} & \onslide<13->{\YES}

\end{tabular}

\end{center}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Specification\\[-1mm] of Matching\end{tabular}}

\large

a regular expression \bl{r} matches a string \bl{s} is defined as

\begin{center}

\bl{s $\in$ $L$(r)}\\ 

\end{center}\bigskip\bigskip\pause

\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 {re1.data};

         \draw[color=green] plot[mark=square*, mark options={fill=white} ] 

		file {re2.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};

	\end{scope}

\end{tikzpicture}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[t]

\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}}

\small

\ldots{}whether a regular expression can match the empty string:

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}

\bl{$nullable(\varnothing)$}      & \bl{$\dn$} & \bl{$f\!\/alse$}\\

\bl{$nullable(\epsilon)$}           & \bl{$\dn$} &  \bl{$true$}\\

\bl{$nullable (c)$}                    & \bl{$\dn$} &  \bl{$f\!alse$}\\

\bl{$nullable (r_1 + r_2)$}       & \bl{$\dn$} &  \bl{$nullable(r_1) \vee nullable(r_2)$} \\ 

\bl{$nullable (r_1 \cdot r_2)$} & \bl{$\dn$} &  \bl{$nullable(r_1) \wedge nullable(r_2)$} \\

\bl{$nullable (r^*)$}                 & \bl{$\dn$} & \bl{$true$} \\

\end{tabular}

\end{center}

\only<2->{

\begin{textblock}{9}(3.4,10)

\begin{tikzpicture}

\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

{\normalsize\color{darkgray}

\begin{minipage}{9cm}

\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont

\texttt{\lstinputlisting{../progs/app5.scala}}}}

\end{minipage}};

\end{tikzpicture}

\end{textblock}}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}

\large

If \bl{r} matches the string \bl{c::s}, what is a regular expression that matches \bl{s}?\bigskip\bigskip\bigskip\bigskip

\small

\bl{$der\,c\,r$} gives the answer

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Derivative of a Rexp (2)\end{tabular}}

\begin{center}

\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}

  \bl{$der\, c\, (\varnothing)$}      & \bl{$\dn$} & \bl{$\varnothing$} & \\

  \bl{$der\, c\, (\epsilon)$}           & \bl{$\dn$} & \bl{$\varnothing$} & \\

  \bl{$der\, c\, (d)$}                     & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\

  \bl{$der\, c\, (r_1 + r_2)$}        & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\

  \bl{$der\, c\, (r_1 \cdot r_2)$}  & \bl{$\dn$}  & \bl{if $nullable (r_1)$}\\

  & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ 

  & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\

  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause

  \bl{$der\!s\, [] r$}     & \bl{$\dn$} & \bl{$r$} & \\

  \bl{$der\!s\, (c\!::\!s) r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\

  \end{tabular}

\end{center}

\only<3->{

\begin{textblock}{10.5}(2,5)

\begin{tikzpicture}

\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] 

{\normalsize\color{darkgray}

\begin{minipage}{10.5cm}

\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont

\texttt{\lstinputlisting{../progs/app6.scala}}}}

\end{minipage}};

\end{tikzpicture}

\end{textblock}}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}}

{\lstset{language=Scala}\fontsize{8}{10}\selectfont

\texttt{\lstinputlisting{../progs/app7.scala}}}

\end{frame}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\mode<presentation>{

\begin{frame}[t]

\frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}}