diff -r e85600529ca5 -r 4794759139ea slides06.tex --- a/slides06.tex Sat Jun 15 09:11:11 2013 -0400 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,579 +0,0 @@ -\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{ -\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{ -\begin{frame}[c] - -``I hate coding. I do not want to look at code.'' - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\begin{frame}[c] - -``I am appalled. You do not show code anymore.'' - -\end{frame}} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - - - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\mode{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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{ -\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: -