--- a/slides/slides02.tex Sun Sep 28 22:30:25 2014 +0100
+++ b/slides/slides02.tex Mon Sep 29 00:45:38 2014 +0100
@@ -12,6 +12,8 @@
numbers=none,
xleftmargin=0mm}
+\pgfplotsset{compat=1.11}
+
\newcommand{\bl}[1]{\textcolor{blue}{#1}}
% beamer stuff
@@ -43,119 +45,154 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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, Strings}
\begin{itemize}
-\item A \alert{language} is a set of strings.\medskip
+\item \alert{\bf Strings} are lists of characters, for example
\begin{center}
-\bl{\{[], hello, foobar, a, abc\}}
+\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\}$}
\end{center}\bigskip
-\item The \alert{meaning} of a regular expression is a set of
- strings, or language.
+\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.
\end{itemize}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}Strings\end{tabular}}
-
-Different ways of writing strings:
-
-\begin{center}
-\begin{tabular}{ccc}
-\bl{\consolas"$hello$"}\quad{} & \bl{$[h, e, l, l, o]$} & \quad\bl{$h\!::\!e\!::\!l\!::\!l\!::\!o\!::\!N\!il$}\bigskip\\
-\bl{\consolas ""} & \bl{$[]$} & \bl{$N$\!$il$}
-\end{tabular}
-\end{center}\pause
-
-The concatenation operation on strings and sets of strings:
-
-\begin{center}
-\begin{tabular}{l}
-\bl{{\consolas"$f\!oo$"}$\;@\;${\consolas"$bar$"}$\;=\;${\consolas"$f\!oobar$"}}\medskip\\
-\bl{$A \;@\; B \dn \{ s_1 @ s_2 \mid s_1 \in A \wedge s_2 \in B\}$}
-\end{tabular}
-\end{center}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[t]
\frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}}
Their inductive definition:
-\begin{textblock}{6}(2,6.5)
+\begin{textblock}{6}(2,7.5)
\begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
\bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\
- & \bl{$\mid$} & \bl{$\epsilon$} & empty string / {\consolas""} / $[]$\\
+ & \bl{$\mid$} & \bl{$\epsilon$} & empty string / \pcode{""} / $[]$\\
& \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)\\
+ & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\
\end{tabular}
\end{textblock}
-\only<2->{
-\begin{textblock}{9}(4,0.5)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
-{\normalsize\color{darkgray}
-\begin{minipage}{9cm}
-\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{../progs/app51.scala}}}}
-\end{minipage}};
-\end{tikzpicture}
+\only<2->{\footnotesize
+\begin{textblock}{9}(2,0.5)
+\begin{bubble}[9.8cm]
+\lstinputlisting{../progs/app01.scala}
+\end{bubble}
\end{textblock}}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\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(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\
- \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)$}\\
+ \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)$}\\
\bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
\bl{$L(r^*)$} & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0} L(r)^n$}\\
\end{tabular}\bigskip
\only<2->{
-\hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{""\}$}\\
+\hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{[]\}$}\\
\textcolor{blue}{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}}
\end{textblock}
-
-
\only<1->{
\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}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
\large
@@ -163,92 +200,112 @@
What is \bl{$L(a^*)$}?
\end{center}
-\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}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\YES}{\textcolor{gray}{yes}}
\newcommand{\NO}{\textcolor{gray}{no}}
\newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}}
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}}
+\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}
-\begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l}
-&\bl{$(a + b) + c$} & \bl{$\equiv^?$} & \bl{$a + (b + c)$} & \onslide<2->{\YES}\\
-&\bl{$a + a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<3->{\YES}\\
-&\bl{$(a \cdot b) \cdot c$} & \bl{$\equiv^?$} & \bl{$a \cdot (b \cdot c)$} & \onslide<4->{\YES}\\
-&\bl{$a \cdot a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<5->{\NO}\\
-&\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\
-&\bl{$\varnothing^*$} & \bl{$\equiv^?$} & \bl{$\varnothing$} & \onslide<7->{\NO}\\
-\FORALLR &\bl{$r \cdot \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<8->{\YES}\\
-\FORALLR &\bl{$r + \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<9->{\NO}\\
-\FORALLR &\bl{$r + \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<10->{\YES}\\
-\FORALLR &\bl{$r \cdot \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<11->{\NO}\\
-&\bl{$c \cdot (a + b)$} & \bl{$\equiv^?$} & \bl{$(c \cdot a) + (c \cdot b)$} & \onslide<12->{\YES}\\
-&\bl{$a^*$} & \bl{$\equiv^?$} & \bl{$\epsilon + (a \cdot a^*)$} & \onslide<13->{\YES}
-\end{tabular}
+\bl{$s \in L(r)$}\\
\end{center}
-\end{frame}}
+\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\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}\bigskip\bigskip\pause
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-\mbox{}\\[-13mm]
-
-\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};
- \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
- file {re-ruby.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};
- \draw[yshift=-\baselineskip, color=brown] (0,0) --
- plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
- node[right]{\small Ruby};
- \end{scope}
+\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}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -278,7 +335,7 @@
\begin{frame}[t]
\frametitle{\begin{tabular}{c}A Matching Algorithm\end{tabular}}
-\small
+
\ldots{}whether a regular expression can match the empty string:
\begin{center}
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
@@ -291,18 +348,6 @@
\end{tabular}
\end{center}
-\only<2->{
-\begin{textblock}{9}(3.4,10)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
-{\normalsize\color{darkgray}
-\begin{minipage}{9cm}
-\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{../progs/app5.scala}}}}
-\end{minipage}};
-\end{tikzpicture}
-\end{textblock}}
-
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -313,7 +358,8 @@
\frametitle{\begin{tabular}{c}The Derivative of a Rexp\end{tabular}}
\large
-If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular expression that matches \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
+If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular
+expression that matches \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
\small
\bl{$der\,c\,r$} gives the answer
@@ -334,25 +380,13 @@
\bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\
& & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\
& & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
- \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause
+ \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\\pause
- \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
- \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\
+ \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
+ \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\
\end{tabular}
\end{center}
-\only<3->{
-\begin{textblock}{10.5}(2,5)
-\begin{tikzpicture}
-\draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm]
-{\normalsize\color{darkgray}
-\begin{minipage}{10.5cm}
-\hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont
-\texttt{\lstinputlisting{../progs/app6.scala}}}}
-\end{minipage}};
-\end{tikzpicture}
-\end{textblock}}
-
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -365,8 +399,9 @@
\begin{center}
\begin{tabular}{l}
-\bl{$der\,a\,r$}\\
-\bl{$der\,b\,r$}
+\bl{$der\,a\,r =?$}\\
+\bl{$der\,b\,r =?$}\\
+\bl{$der\,c\,r =?$}
\end{tabular}
\end{center}
@@ -377,47 +412,189 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\mode<presentation>{
\begin{frame}[t]
+\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]
\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-\mbox{}\\[-13mm]
+\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{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};
+\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}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Solving the Problem\end{tabular}}
+
+What happens if we extend our regular expressions
+
+\begin{center}
+\begin{tabular}{rcl}
+\bl{$r$} & \bl{$::=$} & \bl{\ldots}\\
+ & \bl{$\mid$} & \bl{$r\{n\}$}\\
+ & \bl{$\mid$} & \bl{$r?$}
+\end{tabular}
+\end{center}
+
+What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}?
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
- %plots
- \draw[color=blue] plot[mark=*, mark options={fill=white}]
- file {re-python.data};
- \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
- file {re1.data};
- \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
- file {re-ruby.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};
- \draw[yshift=-\baselineskip, color=brown] (0,0) --
- plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
- node[right]{\small Ruby};
- \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};
- \end{scope}
+\begin{center}
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={\pcode{a}s},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,200,...,1000},
+ xmax=1000,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=9.5cm,
+ height=7cm,
+ legend entries={Python,Ruby,Scala V1,Scala V2},
+ 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};
+\addplot[red,mark=triangle*,mark options={fill=white}]
+ table {re1.data};
+\addplot[green,mark=square*,mark options={fill=white}]
+ table {re2b.data};
+\end{axis}
\end{tikzpicture}
+\end{center}
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Examples\end{tabular}}
+
+Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with
+
+\begin{center}
+\begin{tabular}{l}
+\bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\
+\bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$}\\
+\bl{$der\,c\,r = ((\varnothing \cdot b) + \varnothing)\cdot r$}
+\end{tabular}
+\end{center}
+
+What are these regular expressions equivalent to?
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[t]
+\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
+
+\begin{center}
+\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=9cm,
+ height=7cm
+]
+\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{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -471,7 +648,7 @@
Assume \bl{$P(r)$} is the property:
\begin{center}
-\bl{$nullable(r)$} if and only if \bl{$"" \in L(r)$}
+\bl{$nullable(r)$} if and only if \bl{$[] \in L(r)$}
\end{center}
\end{frame}}
@@ -482,6 +659,35 @@
\begin{frame}[c]
\frametitle{\begin{tabular}{c}Proofs about Rexp (4)\end{tabular}}
+
+\begin{center}
+\bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
+$rev(\varnothing)$ & $\dn$ & $\varnothing$\\
+$rev(\epsilon)$ & $\dn$ & $\epsilon$\\
+$rev(c)$ & $\dn$ & $c$\\
+$rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\
+$rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
+$rev(r^*)$ & $\dn$ & $rev(r)^*$\\
+\end{tabular}}
+\end{center}
+
+
+We can prove
+
+\begin{center}
+\bl{$L(rev(r)) = \{s^{-1} \;|\; s \in L(r)\}$}
+\end{center}
+
+by induction on \bl{$r$}.
+
+\end{frame}}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\mode<presentation>{
+\begin{frame}[c]
+\frametitle{\begin{tabular}{c}Proofs about Rexp (5)\end{tabular}}
+
Let \bl{$Der\,c\,A$} be the set defined as
\begin{center}
@@ -523,281 +729,13 @@
We can finally prove
\begin{center}
-\bl{$matcher(r, s)$} if and only if \bl{$s \in L(r)$}
+\bl{$matches(r, s)$} if and only if \bl{$s \in L(r)$}
\end{center}
\end{frame}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-13mm]
-
-\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};
- \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
- file {re1.data};
- \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
- file {re-ruby.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};
- \draw[yshift=-\baselineskip, color=brown] (0,0) --
- plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
- node[right]{\small Ruby};
- \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};
- \end{scope}
-\end{tikzpicture}
-
-\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}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Solving the Problem\end{tabular}}
-
-What happens if we extend our regular expressions
-
-\begin{center}
-\begin{tabular}{rcl}
-\bl{$r$} & \bl{$::=$} & \bl{\ldots}\\
- & \bl{$\mid$} & \bl{$r\{n\}$}\\
- & \bl{$\mid$} & \bl{$r?$}
-\end{tabular}
-\end{center}
-
-What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}?
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-13mm]
-
-\begin{tikzpicture}[y=.2cm, x=.12cm]
- %axis
- \draw (0,0) -- coordinate (x axis mid) (70,0);
- \draw (0,0) -- coordinate (y axis mid) (0,30);
- %ticks
- \foreach \x in {0,10,...,70}
- \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};
- \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
- file {re1.data};
- \draw[color=green] plot[mark=square*, mark options={fill=white} ]
- file {re2a.data};
- \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
- file {re-ruby.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};
- \draw[yshift=-\baselineskip, color=brown] (0,0) --
- plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0)
- node[right]{\small Ruby};
- \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};
- \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};
- \end{scope}
-\end{tikzpicture}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-13mm]
-
-\begin{tabular}{@ {\hspace{-5mm}}l}
-\begin{tikzpicture}[y=.2cm, x=.01cm]
- %axis
- \draw (0,0) -- coordinate (x axis mid) (1000,0);
- \draw (0,0) -- coordinate (y axis mid) (0,30);
- %ticks
- \foreach \x in {0,100,...,1000}
- \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};
- \draw[color=red] plot[mark=triangle*, mark options={fill=white} ]
- file {re1.data};
- \draw[color=green] plot[mark=square*, mark options={fill=white} ]
- file {re2b.data};
- \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ]
- file {re-ruby.data};
-
- %legend
- \begin{scope}[shift={(100,20)}]
- \draw[color=blue] (0,0) --
- plot[mark=*, mark options={fill=white}] (0.25,0) -- (50,0)
- node[right]{\small Python};
- \draw[yshift=-13, color=brown] (0,0) --
- plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (50,0)
- node[right]{\small Ruby};
- \draw[yshift=13, color=red] (0,0) --
- plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0)
- node[right]{\small Scala V1};
- \draw[yshift=26, color=green] (0,0) --
- plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0)
- node[right]{\small Scala V2};
- \end{scope}
-\end{tikzpicture}
-\end{tabular}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[c]
-\frametitle{\begin{tabular}{c}Examples\end{tabular}}
-
-Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with
-
-\begin{center}
-\begin{tabular}{l}
-\bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\
-\bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$}
-\end{tabular}
-\end{center}
-
-What are these regular expressions equal to?
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\mode<presentation>{
-\begin{frame}[t]
-\frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}}
-
-\mbox{}\\[-9mm]
-
-\begin{tabular}{@ {\hspace{-5mm}}l}
-\begin{tikzpicture}[y=.2cm, x=.0008cm]
- %axis
- \draw (0,0) -- coordinate (x axis mid) (12000,0);
- \draw (0,0) -- coordinate (y axis mid) (0,30);
- %ticks
- \foreach \x in {0,2000,...,12000}
- \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=red] plot[mark=triangle*, mark options={fill=white} ]
- file {re1.data};
- \draw[color=green] plot[mark=square*, mark options={fill=white} ]
- file {re2b.data};
- \draw[color=black] plot[mark=square*, mark options={fill=white} ]
- file {re3.data};
-
- %legend
- \begin{scope}[shift={(2000,20)}]
- \draw[color=red] (0,0) --
- plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0)
- node[right]{\small Scala V1};
- \draw[yshift=13, color=green] (0,0) --
- plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0)
- node[right]{\small Scala V2};
- \draw[yshift=26, color=black] (0,0) --
- plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0)
- node[right]{\small Scala V3};
- \end{scope}
-\end{tikzpicture}
-\end{tabular}
-
-\end{frame}}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
\end{document}
%%% Local Variables: