\documentclass[dvipsnames,14pt,t]{beamer}

\usepackage{beamerthemeplainculight}

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

\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

\lstset{language=Java,

	basicstyle=\ttfamily,

	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=\ttfamily,

	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 06, King's College London, 31.~October 2012}

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

1  0.00240

2  0.00013

3  0.00020

4  0.00030

5  0.00049

6  0.00083

7  0.00146

8  0.00228

9  0.00351

10  0.00640

11  0.01217

12  0.02565

13  0.01382

14  0.02423

15  0.05065 

16  0.06522

17  0.02140

18  0.05176

19  0.18254

20  0.51898

21  1.39631

22  2.69501

23  8.07952

\end{filecontents}

\begin{filecontents}{re-internal.data}

1 0.00069

301 0.00700

601 0.00297

901 0.00470

1201 0.01301

1501 0.01175

1801 0.01761

2101 0.01787

2401 0.02717

2701 0.03932

3001 0.03470

3301 0.04349

3601 0.05411

3901 0.06181

4201 0.07119

4501 0.08578

\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

\end{filecontents}

\begin{document}

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

\mode<presentation>{

\begin{frame}<1>[t]

\frametitle{%

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

  \\[-3mm]

  \LARGE Automata and \\[-2mm] 

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

  \end{tabular}}

  \normalsize

  \begin{center}

  \begin{tabular}{ll}

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

  Of$\!$fice: & S1.27 (1st floor Strand Building)\\

  Slides: & KEATS (also home work is there)\\

  \end{tabular}

  \end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

``I hate coding. I do not want to look at code.''

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

``I am appalled. You do not show code anymore.''

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

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

\begin{itemize}

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

\item ``Regular Expressions Will Stab You in the Back''\bigskip

\item Evil regular expressions\medskip

\begin{itemize}

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

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

\item \bl{$([a-zA-Z]^+)^*$}

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

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

\end{itemize}

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Regexp Matching\end{tabular}}

Given a regular expression

\begin{enumerate}

\item you might convert it into a DFA (subset construction)

\item you might try all possible paths in an NFA via backtracking

\item you might try all paths in an NFA in parallel

\item you might try to convert the DFA ``lazily''

\end{enumerate}\bigskip

Often No~2 is implemented (sometimes there are even good reasons for doing this).

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}\bl{$(a?\{n\})a\{n\}$} in Python\end{tabular}}

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

	\only<2->{

	\draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 

		file {re1.data};}

	\only<3->{	 

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

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

	\only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- 

		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)

		node[right]{\small Scala V1};}

	\only<3->{	

	 \draw[yshift=2\baselineskip, color=green] (0,0) -- 

		plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0)

		node[right]{\small Scala V2 with simplifications};}

	\end{scope}

\end{tikzpicture}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\begin{tikzpicture}[y=.7cm, x=.0009cm]

 	%axis

	\draw (0,0) -- coordinate (x axis mid) (10000,0);

    	\draw (0,0) -- coordinate (y axis mid) (0,6);

    	%ticks

    	\foreach \x in {0,2000,...,10000}

     		\draw (\x,1pt) -- (\x,-3pt)

			node[anchor=north] {\x};

    	\foreach \y in {0,1,...,6}

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

	\only<2->{	 

         \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] 

		file {re3.data};}

	%legend

	\begin{scope}[shift={(2000,4)}] 

	\draw[color=blue] (0,0) -- 

		plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) 

		node[right]{\small Scala Internal};

        \only<2->{

	\draw[yshift=\baselineskip, color=red] (0,0) -- 

		plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0)

		node[right]{\small Scala V3 with explicit $\_\{\_\}$};}

	\end{scope}

\end{tikzpicture}

\end{frame}}

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

\newcommand{\qq}{\mbox{\texttt{"}}}

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

\mode<presentation>{

\begin{frame}[c]

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

A (context-free) grammar \bl{$G$} consists of

\begin{itemize}

\item a finite set of nonterminal symbols (upper case)

\item a finite terminal symbols or tokens (lower case)

\item a start symbol (which must be a nonterminal)

\item a set of rules

\begin{center}

\bl{$A \rightarrow \text{rhs}$}

\end{center}

where \bl{rhs} are sequences involving terminals and nonterminals.\medskip\pause

We can also allow rules

\begin{center}

\bl{$A \rightarrow \text{rhs}_1 | \text{rhs}_2 | \ldots$}

\end{center}

\end{itemize}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

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

\begin{center}

\bl{\begin{tabular}{lcl}

$S$ & $\rightarrow$ &  $\epsilon$ \\

$S$ & $\rightarrow$ &  $a\cdot S\cdot a$ \\

$S$ & $\rightarrow$ &  $b\cdot S\cdot b$ \\

\end{tabular}}

\end{center}\pause

or

\begin{center}

\bl{\begin{tabular}{lcl}

$S$ & $\rightarrow$ &  $\epsilon \;|\; a\cdot S\cdot a \;|\;b\cdot S\cdot b$ \\

\end{tabular}}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

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

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $num\_token$ \\

$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

$E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

\end{tabular}}

\end{center}\pause

\bl{\texttt{1 + 2 * 3 + 4}}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Parse Trees\end{tabular}}

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $F \;|\; F \cdot * \cdot F$\\

$F$ & $\rightarrow$ & $T \;|\; T \cdot + \cdot T \;|\; T \cdot - \cdot T$\\

$T$ & $\rightarrow$ & $num\_token \;|\; ( \cdot E \cdot )$\\

\end{tabular}}

\end{center}

\begin{center}

\begin{tikzpicture}[level distance=8mm, blue]

  \node {$E$}

    child {node {$F$} 

     child {node {$T$} 

                 child {node {(\,$E$\,)}

                            child {node{$F$ *{} $F$}

                                  child {node {$T$} child {node {2}}}

                                  child {node {$T$} child {node {3}}} 

                               }

                          }

              }

     child {node {+}}

     child {node {$T$}

       child {node {(\,$E$\,)} 

       child {node {$F$}

       child {node {$T$ +{} $T$}

                    child {node {3}}

                    child {node {4}} 

                 }

                 }}

    }};

\end{tikzpicture}

\end{center}

\begin{textblock}{5}(1, 6.5)

\bl{\texttt{(2*3)+(3+4)}}

\end{textblock}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}Ambiguous Grammars\end{tabular}}

A grammar is \alert{ambiguous} if there is a string that has at least parse trees.

\begin{center}

\bl{\begin{tabular}{lcl}

$E$ & $\rightarrow$ &  $num\_token$ \\

$E$ & $\rightarrow$ &  $E \cdot + \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot - \cdot E$ \\

$E$ & $\rightarrow$ &  $E \cdot * \cdot E$ \\

$E$ & $\rightarrow$ &  $( \cdot E \cdot )$ 

\end{tabular}}

\end{center}

\bl{\texttt{1 + 2 * 3 + 4}}

\end{frame}}

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

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

\mode<presentation>{