\pgfplotsset{compat=1.11}

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

\item \alert{\bf Strings} are lists of characters, for example

\bl{$[]$},\;\bl{$abc$}  \hspace{2cm}(Pattern match: \bl{$c\!::\!s$})

\end{center}\bigskip

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

\begin{center}

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

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

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

%\item The \alert{\bf meaning} of a regular expression is a set of 

%  strings, or language.

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

         & \bl{$\mid$} & \bl{$\epsilon$}       & empty string / \pcode{""} / $[]$\\

         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\

\only<2->{\footnotesize

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

\begin{bubble}[9.8cm]

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

\end{bubble}

\end{frame}

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

\hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{[]\}$}\\

\end{frame}

\end{frame}

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

\begin{frame}[t]

\frametitle{\begin{tabular}{c}Concrete Equivalences\end{tabular}}

\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{\begin{tabular}{c}Corner Cases\end{tabular}}

\begin{center}

\bl{\begin{tabular}{rcl}

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

$a + \epsilon$ & $\not\equiv$ & $a$\\

$\epsilon$ & $\equiv$ & $\varnothing^*$\\

$\epsilon^*$ & $\equiv$ & $\epsilon$\\

$\varnothing^*$ & $\not\equiv$ & $\varnothing$\\

\end{tabular}}

\end{center}

\end{frame}

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

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

\begin{frame}[t]

\frametitle{\begin{tabular}{c}Simplification Rules\end{tabular}}

\begin{center}

\bl{\begin{tabular}{rcl}

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

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

$r \cdot \epsilon$ & $\equiv$ & $r$\\

$\epsilon \cdot r$     & $\equiv$ & $r$\\

$r \cdot \varnothing$ & $\equiv$ & $\varnothing$\\

$\varnothing \cdot r$ & $\equiv$ & $\varnothing$\\

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

\end{tabular}}

\end{center}

\end{frame}

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

\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

\bl{$s \in L(r)$}\\ 

\end{frame}

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

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

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

  \bl{$der\, c\, (r^*)$}          & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\\pause

  \bl{$\textit{ders}\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\

  \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\

\bl{$der\,a\,r =?$}\\

\bl{$der\,b\,r =?$}\\

\bl{$der\,c\,r =?$}

\frametitle{The Algorithm}

\begin{center}

\begin{tabular}{@{}rll@{}}

Input: & \bl{$r_1$}, \bl{$abc$}\medskip\\

Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = der\,a\,r_1)$}\smallskip\\

Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = der\,b\,r_2)$}\smallskip\\

Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = der\,b\,r_3)$}\smallskip\\

Step 4: & the string is exhausted; test & (\bl{$nullable(r_4)$})\\

        & whether \bl{$r_4$} can recognise\\

        & the empty string\smallskip\\

Output: & result of the test\\

        & $\Rightarrow true \,\text{or}\, \textit{false}$\\        

\end{tabular}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

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

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

    scaled ticks=false,

    axis lines=left,

    width=7cm,

    height=7cm, 

    legend entries={Python,Ruby,Scala V1},  

    legend pos=outer north east,

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

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

  table {re1.data};  

\end{axis}

\end{tikzpicture}

\end{center}

\end{frame}}

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

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

\mode<presentation>{

\begin{frame}[c]

\frametitle{\begin{tabular}{c}A Problem\end{tabular}}

We represented the ``n-times'' \bl{$a\{n\}$} as a sequence regular expression:

\begin{center}

\begin{tabular}{rl}

1: & \bl{$a$}\\

2: & \bl{$a\cdot a$}\\

3: & \bl{$a\cdot a\cdot a$}\\

& \ldots\\

13: & \bl{$a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a$}\\

& \ldots\\

20:

\end{tabular}

\end{center}

This problem is aggravated with \bl{$a?$} being represented as \bl{$\epsilon + a$}.

\end{frame}}

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