--- a/slides/slides02.tex Sat Oct 01 23:34:37 2016 +0100
+++ b/slides/slides02.tex Sun Oct 02 14:07:42 2016 +0100
@@ -51,55 +51,58 @@
\footnotesize
\begin{center}
+ {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\\
\begin{tabular}{@{}cc@{}}
\begin{tikzpicture}
\begin{axis}[
- xlabel={\pcode{a}s},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,5,...,30},
- xmax=30,
+ xmax=33,
ymax=35,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
- width=4.5cm,
+ width=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};
+\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},
+ \begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.1,0.05)}},
ylabel={time in secs},
enlargelimits=false,
- xtick={0,3000,...,12000},
- xmax=12000,
+ xtick={0,4000,...,12000},
+ xmax=13500,
ymax=35,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
- width=5.5cm,
+ width=5cm,
height=4.5cm
]
-\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
+\addplot[green,mark=square*,mark options={fill=white}] table {re2.data};
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
\end{axis}
\end{tikzpicture}
\end{tabular}
\end{center}
+\small
+In the handouts is a similar graph with \bl{$(a^*)^* \cdot b$} for Java.
\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -108,7 +111,7 @@
\begin{itemize}
-\item A \alert{\bf language} is a set of strings, for example\medskip
+\item A \alert{\bf Language} is a set of strings, for example\medskip
\begin{center}
\bl{$\{[], hello, \textit{foobar}, a, abc\}$}
\end{center}\bigskip
@@ -228,23 +231,23 @@
\bigskip
\begin{center}
-\bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ }
+\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}\}$\\
-$Der\,a\,A$ & $=$ & $\{\}$\\\pause
+$\Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\
+$\Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\
+$\Der\,a\,A$ & $=$ & $\{\}$\\\pause
\end{tabular}}
\end{center}
\small
We can extend this definition to strings
\[
-\bl{Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}}
+\bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}}
\]
\end{itemize}
@@ -404,22 +407,24 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} and \bl{$(a^*)^* \cdot b$}}
-\begin{center}
+\begin{center}\footnotesize
+\begin{tabular}{@{}c@{\hspace{-2mm}}c@{}}
\begin{tikzpicture}
\begin{axis}[
- xlabel={\pcode{a}s},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,5,...,30},
- xmax=30,
+ xmax=33,
ymax=35,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
- width=9cm,
- height=7cm,
+ width=5.5cm,
+ height=4.5cm,
legend entries={Python,Ruby},
legend pos=north west,
legend cell align=left
@@ -430,6 +435,28 @@
table {re-ruby.data};
\end{axis}
\end{tikzpicture}
+&
+\begin{tikzpicture}
+\begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,5,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=5.5cm,
+ height=4.5cm,
+ legend entries={Java},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\end{axis}
+\end{tikzpicture}
+\end{tabular}
\end{center}
\end{frame}
@@ -444,10 +471,10 @@
\item Evil regular expressions\medskip
\begin{itemize}
\item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}
-\item \bl{$(a^+)^+$}
+\item \bl{$(a^*)^*$}
\item \bl{$([a$\,-\,$z]^+)^*$}
-\item \bl{$(a + a \cdot a)^+$}
-\item \bl{$(a + a?)^+$}
+\item \bl{$(a + a \cdot a)^*$}
+\item \bl{$(a + a?)^*$}
\end{itemize}
\end{itemize}
@@ -484,7 +511,7 @@
expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip
\small
-\bl{$der\,c\,r$} gives the answer, Brzozowski 1964
+\bl{$\der\,c\,r$} gives the answer, Brzozowski 1964
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -494,17 +521,17 @@
\begin{center}
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
- \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
- \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
- \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
- \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
- \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^*)$} &\bigskip\\\pause
+ \bl{$\der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$\der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
+ \bl{$\der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
+ \bl{$\der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$\der\, c\, r_1 + \der\, c\, r_2$} & \\
+ \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^*)$} &\bigskip\\\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{$\ders\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
+ \bl{$\ders\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\ders\,s\,(\der\,c\,r)$} & \\
\end{tabular}
\end{center}
@@ -519,9 +546,9 @@
\begin{center}
\begin{tabular}{l}
-\bl{$der\,a\,r =\;?$}\\
-\bl{$der\,b\,r =\;?$}\\
-\bl{$der\,c\,r =\;?$}
+\bl{$\der\,a\,r =\;?$}\\
+\bl{$\der\,b\,r =\;?$}\\
+\bl{$\der\,c\,r =\;?$}
\end{tabular}
\end{center}
@@ -533,8 +560,8 @@
\frametitle{The Algorithm}
\begin{center}
-\begin{tabular}{l}
-\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\textit{ders}\,r\,s)$}
+\begin{tabular}{l}
+\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\,r\,s)$}
\end{tabular}
\end{center}
@@ -544,16 +571,16 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
-\frametitle{The Algorithm}
+\frametitle{An Example}
+Does \bl{$r_1$} match \bl{$abc$}?
\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\\
+\begin{tabular}{@{}rl@{}l@{}}
+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\,c\,r_3)$}\smallskip\\
+Step 4: & the string is exhausted: & \bl{($nullable(r_4))$}\\
+ & test whether \bl{$r_4$} can recognise\\
& the empty string\smallskip\\
Output: & result of the test\\
& $\Rightarrow \bl{\textit{true}} \,\text{or}\,
@@ -573,11 +600,11 @@
expression \bl{$r_1$} then\medskip
\begin{enumerate}
-\item \bl{$Der\,a\,(L(r_1))$}\pause
-\item \bl{$Der\,b\,(Der\,a\,(L(r_1)))$}\pause
-\item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r_1))))$}\bigskip
+\item \bl{$\Der\,a\,(L(r_1))$}\pause
+\item \bl{$\Der\,b\,(\Der\,a\,(L(r_1)))$}\pause
+\item \bl{$\Der\,c\,(\Der\,b\,(\Der\,a\,(L(r_1))))$}\bigskip
\item finally we test whether the empty string is in this
-set; same for \bl{$Ders\,abc\,(L(r_1))$}.\medskip
+set; same for \bl{$\Ders\,abc\,(L(r_1))$}.\medskip
\end{enumerate}
The matching algorithm works similarly, just over regular expressions instead of sets.
@@ -587,16 +614,17 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
+\frametitle{Oops\ldots\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
\begin{center}
\begin{tikzpicture}
\begin{axis}[
- xlabel={\pcode{a}s},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,5,...,30},
- xmax=30,
+ xmax=31,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
@@ -639,7 +667,7 @@
\end{center}
This problem is aggravated with \bl{$a^?$} being represented
-as \bl{$\ONE + a$}.
+as \bl{$a + \ONE$}.
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -657,7 +685,8 @@
\end{tabular}
\end{center}
-What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}?
+What is their meaning?\\
+What are the cases for \bl{$nullable$} and \bl{$\der$}?
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -669,11 +698,12 @@
\begin{center}
\begin{tikzpicture}
\begin{axis}[
- xlabel={\pcode{a}s},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,200,...,1000},
- xmax=1000,
+ xmax=1100,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
@@ -707,9 +737,9 @@
\begin{center}
\begin{tabular}{l}
-\bl{$der\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$}\\
-\bl{$der\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$}\\
-\bl{$der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$}
+\bl{$\der\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$}\\
+\bl{$\der\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$}\\
+\bl{$\der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$}
\end{tabular}
\end{center}
@@ -719,7 +749,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}}
@@ -727,17 +756,20 @@
\begin{center}
\begin{tikzpicture}
\begin{axis}[
- xlabel={\pcode{a}s},
+ xlabel={$n$},
+ x label style={at={(1.05,0.0)}},
ylabel={time in secs},
enlargelimits=false,
xtick={0,3000,...,12000},
- xmax=12000,
+ xmax=14000,
ymax=35,
ytick={0,5,...,30},
scaled ticks=false,
axis lines=left,
width=9cm,
- height=7cm
+ height=7cm,
+ legend entries={Scala V2,Scala V3},
+ legend pos=north east
]
\addplot[green,mark=square*,mark options={fill=white}] table {re2b.data};
\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
@@ -749,6 +781,40 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\bl{$(a^*)^* \cdot b$}}
+
+\begin{center}
+\begin{tikzpicture}
+ \begin{axis}[
+ xlabel={$n$},
+ x label style={at={(1.09,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xmax=5000,
+ xtick={0,2000,...,6000},
+ ytick={0,5,...,10},
+ ymax=15,
+ scaled ticks=false,
+ axis lines=left,
+ width=9cm,
+ height=5cm,
+ legend entries={Scala V3},
+ legend pos=north west,
+ legend cell align=left]
+\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data};
+%%where is 2nd graph
+%%\addplot[black,mark=square*,mark options={fill=white}] table {re3.data};
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{What is good about this Alg.}
@@ -857,17 +923,17 @@
\begin{center}
\begin{tabular}{rp{4cm}}
& \bl{$s \in L(r)$}\medskip\\
-\bl{$\Leftrightarrow$} & \bl{$[] \in Ders\,s\,(L(r))$}\pause
+\bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause
\end{tabular}
\end{center}
-\item if we can show \bl{$Ders\, s\,(L(r)) = L(ders\,s\,r)$} we
+\item if we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we
have
\begin{center}
\begin{tabular}{rp{4cm}}
-\bl{$\Leftrightarrow$} & \bl{$[] \in L(ders\,s\,r)$}\medskip\\
-\bl{$\Leftrightarrow$} & \bl{$nullable(ders\,s\,r)$}\medskip\\
+\bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
+\bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
\bl{$\dn$} & \bl{$matches\,s\,r$}
\end{tabular}
\end{center}
@@ -884,13 +950,13 @@
Let \bl{$Der\,c\,A$} be the set defined as
\begin{center}
-\bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ }
+\bl{$\Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ }
\end{center}
We can prove
\begin{center}
-\bl{$L(der\,c\,r) = Der\,c\,(L(r))$}
+\bl{$L(\der\,c\,r) = \Der\,c\,(L(r))$}
\end{center}
by induction on \bl{$r$}.
@@ -919,7 +985,7 @@
We can then prove
\begin{center}
-\bl{$Ders\,s\,(L(r)) = L(ders\,s\,r)$}
+\bl{$\Ders\,s\,(L(r)) = L(\ders\,s\,r)$}
\end{center}