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

\usepackage{../slides}

\usepackage{../graphics}

\usepackage{../langs}

\usepackage{../data}

\hfuzz=220pt 

\lstset{language=Scala,

        style=mystyle,

        numbersep=0pt,

        numbers=none,

        xleftmargin=0mm}

\pgfplotsset{compat=1.12}

\newcommand{\bl}[1]{\textcolor{blue}{#1}}     

% beamer stuff 

\begin{document}

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

\begin{frame}[t]

\frametitle{%

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

  \\[-3mm]

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

  \end{tabular}}

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

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

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

\begin{frame}[c]

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

    An Efficient Regular\\[-1mm] 

    Expression Matcher\end{tabular}}

\footnotesize

\begin{center}

\begin{tabular}{@{}cc@{}}

\begin{tikzpicture}

\begin{axis}[

    xlabel={\pcode{a}s},

    ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=30,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=4.5cm,

    height=4.5cm, 

    legend entries={Python,Ruby},  

    legend pos=north west,

    legend cell align=left  

]

\addplot[blue,mark=*, mark options={fill=white}] 

  table {re-python.data};

\addplot[brown,mark=pentagon*, mark options={fill=white}] 

  table {re-ruby.data};  

\end{axis}

\end{tikzpicture}

&

\begin{tikzpicture}

\begin{axis}[

    xlabel={\pcode{a}s},

    ylabel={time in secs},

    enlargelimits=false,

    xtick={0,3000,...,12000},

    xmax=12000,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=5.5cm,

    height=4.5cm

]

\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};

\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};

\end{axis}

\end{tikzpicture}

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Languages}

\begin{itemize}

\item A \alert{\bf language} is a set of strings, for example\medskip

\begin{center}

\bl{$\{[], hello, \textit{foobar}, a, abc\}$}

\end{center}\bigskip

\item \alert{\bf Concatenation} of strings and languages

\begin{center}

\begin{tabular}{rcl}

\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\

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

\end{tabular}

\end{center}

\bigskip

\small

\item [] For example \bl{$A = \{foo, bar\}$}, \bl{$B = \{a, b\}$}

\[

\bl{A \,@\, B = \{fooa, foob, bara, barb\}}

\]

\end{itemize}  

\end{frame}

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

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

\begin{frame}[c]

\frametitle{The Power Operation}

\begin{itemize}

\item The \alert{\bf Power} of a language:

\begin{center}

\begin{tabular}{lcl}

\bl{$A^0$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\

\bl{$A^{n+1}$} & \bl{$\dn$} & \bl{$A \,@\, A^n$}

\end{tabular}

\end{center}\bigskip

\item[] For example

\begin{center}

\begin{tabular}{l}

\bl{$A^4 = A \,@\, A \,@\, A \,@\, A$}\\

\bl{$A^0 \dn \{[]\}$}\\

\end{tabular}

\end{center}

\end{itemize}  

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Homework Question}

\begin{itemize}

\item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip

\begin{center}

How many strings are in \bl{$A^4$}?

\end{center}\bigskip\medskip\pause

\begin{center}

\begin{tabular}{l}

What if \bl{$A = \{[a],[b],[c],[]\}$};\\ 

how many strings are then in \bl{$A^4$}?

\end{tabular}

\end{center}

\end{itemize}  

\end{frame}

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

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

\begin{frame}[c]

\frametitle{The Star Operation}

\begin{itemize}

\item The \alert{\bf Star} of a \underline{language}:

\bigskip

\begin{center}

\begin{tabular}{c}

\bl{$A^* \dn \bigcup_{0\le n} A^n$}

\end{tabular}

\end{center}\bigskip

\item[] This expands to 

\[

\bl{A^0 \cup A^1 \cup A^2 \cup A^3 \cup A^4 \cup \ldots}

\]

\small

\[

\bl{\{[]\} \;\cup\; A \;\cup\; A\,@\,A \;\cup\; 

  A\,@\,A\,@\,A \;\cup\; A\,@\,A\,@\,A\,@\,A \cup \ldots}

\]

\end{itemize}  

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Semantic Derivative}

\begin{itemize}

\item The \alert{\bf Semantic Derivative} of a 

\underline{language}\\ wrt to a character \bl{$c$}:

\bigskip

\begin{center}

\bl{$Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$ } 

\end{center}\bigskip\bigskip\bigskip

For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then

\begin{center}

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

$Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\

$Der\,b\,A$ & $=$ &  $\{\textit{ar}\}$\\  

\end{tabular}}

\end{center}

\small

We can extend this definition to strings

\[

\bl{Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}}

\]

\end{itemize}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Regular Expressions}

Their inductive definition:

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

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

         & \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->{\footnotesize

\begin{textblock}{9}(2,0.5)

\begin{bubble}[9.8cm]

\lstinputlisting{../progs/app01.scala}

\end{bubble}

\end{textblock}}  

\end{frame}

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

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

\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(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{$(L(r))^*$}\\

 \end{tabular}

\end{textblock}

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

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

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

\begin{frame}[c]

\large

\begin{center}

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

\end{center}  

\end{frame}

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

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

\begin{frame}[c]

\frametitle{\begin{tabular}{c}

 When Are Two Regular\\[-1mm]

 Expressions Equivalent?\end{tabular}}

\large

\begin{center}

\bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$}

\end{center}  

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Concrete Equivalences}

\begin{center}

\bl{\begin{tabular}{rcl}

$(a + b)  + c$ & $\equiv$ & $a + (b + c)$\\

$a + a$        & $\equiv$ & $a$\\

$a + b$        & $\equiv$ & $b + a$\\

$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\

$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause

$a \cdot a$       & $\not\equiv$ & $a$\\

$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\

\end{tabular}}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Corner Cases}

\begin{center}

\bl{\begin{tabular}{rcl}

\end{tabular}}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{Simplification Rules}

\begin{center}

\bl{\begin{tabular}{rcl}

$r + r$ & $\equiv$ & $r$

\end{tabular}}

\end{center}

\end{frame}

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

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

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

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

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

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

\end{frame}

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

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

\begin{frame}[c]

\begin{center}

\begin{tikzpicture}

\begin{axis}[

    xlabel={\pcode{a}s},

    ylabel={time in secs},

    enlargelimits=false,

    xtick={0,5,...,30},

    xmax=30,

    ymax=35,

    ytick={0,5,...,30},

    scaled ticks=false,

    axis lines=left,

    width=9cm,

    height=7cm, 

    legend entries={Python,Ruby},  

    legend pos=north west,

    legend cell align=left  

]

\addplot[blue,mark=*, mark options={fill=white}] 

  table {re-python.data};

\addplot[brown,mark=pentagon*, mark options={fill=white}] 

  table {re-ruby.data};  

\end{axis}

\end{tikzpicture}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{Evil Regular Expressions}

\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^+)^+$}

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

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

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

\end{itemize}

\end{itemize}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{A Matching Algorithm}

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

\begin{center}

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

\bl{$nullable (c)$}             & \bl{$\dn$} & \bl{\textit{false}}\\

\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{\textit{true}}\\

\end{tabular}

\end{center}

\end{frame}

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

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

\begin{frame}[c]

\frametitle{The Derivative of a Rexp}

\large

If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular 

expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip

\small

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

\end{frame}

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