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

1 0.00179

2 0.00011

3 0.00014

4 0.00026

5 0.00050

6 0.00095

7 0.00190

8 0.00287

9 0.00779

10 0.01399

11 0.01894

12 0.03666

13 0.07994

14 0.08944

15 0.02377

16 0.07392

17 0.22798

18 0.65310

19 2.11360

20 6.31606

21 21.46013

\end{filecontents}

\begin{filecontents}{re2a.data}

1 0.00227

5 0.00027

10 0.00075

15 0.00178

20 0.00102

25 0.00028

30 0.00040

35 0.00052

40 0.00075

45 0.00125

50 0.00112

55 0.00099

60 0.00113

65 0.00137

70 0.00170

\end{filecontents}

\begin{filecontents}{re2b.data}

1 0.00020

51 0.00080

101 0.00678

151 0.01792

201 0.04815

251 0.09648

301 0.23195

351 0.52646

401 0.96277

451 1.57726

501 2.00166

551 2.98341

601 4.81181

651 6.57054

701 9.73973

751 14.25762

801 14.80760

851 19.60958

901 25.43550

951 31.96038

\end{filecontents}

\begin{filecontents}{re3.data}

1 0.001605

501 0.131066

1001 0.057885

1501 0.136875

2001 0.176238

2501 0.254363

3001 0.37262

3501 0.500946

4001 0.638384

4501 0.816605

5001 1.00491

5501 1.232505

6001 1.525672

6501 1.757502

7001 2.092784

7501 2.429224

8001 2.803037

8501 3.463045

9001 3.609

9501 4.081504

10001 4.54569

10501 6.17789

11001 6.77242

11501 7.95864

\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] for Matching\end{tabular}}

\large

a regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if

\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=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}[c]

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

\begin{itemize}

\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip

\item Evil regular expressions\medskip

\begin{itemize}

\item \bl{$(a?\{n\}) \cdot a\{n\}$}

\item \bl{$(a^+)^+$}

\item \bl{$([a$\,-\,$z]^+)^*$}

\item \bl{$(a + a \cdot a)^+$}

\item \bl{$(a + a?)^+$}

\end{itemize}

\end{itemize}

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