\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>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Chomsky Normal Form\end{tabular}}
All rules must be of the form
\begin{center}
\bl{$A \rightarrow a$}
\end{center}
or
\begin{center}
\bl{$A \rightarrow B\cdot C$}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
\begin{center}
\bl{\begin{tabular}{@ {}lcl}
$S$ & $\rightarrow$ & $N\cdot P$ \\
$P$ & $\rightarrow$ & $V\cdot N$ \\
$N$ & $\rightarrow$ & $N\cdot N$ \\
$N$ & $\rightarrow$ & $\texttt{students} \;|\; \texttt{Jeff} \;|\; \texttt{geometry} \;|\; \texttt{trains} $ \\
$V$ & $\rightarrow$ & $\texttt{trains}$
\end{tabular}}
\end{center}
\bl{\texttt{Jeff trains geometry students}}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[c]
\frametitle{\begin{tabular}{c}CYK Algorithm\end{tabular}}
\begin{itemize}
\item runtime is \bl{$O(n^3)$}\bigskip
\item grammars need to be transferred into CNF
\end{itemize}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: