--- a/slides/slides03.tex Sun Oct 11 09:10:08 2020 +0100
+++ b/slides/slides03.tex Tue Oct 13 14:29:10 2020 +0100
@@ -241,13 +241,14 @@
Non-Deterministic\\[-1mm]
Finite Automata\end{tabular}}
-A non-deterministic finite automaton (NFA) consists again of:
+\bl{$N(\varSigma, \mbox{Qs}, \mbox{Qs}_0, F, \rho)$}\\
+A non-deterministic finite automaton (NFA) consists of:
\begin{itemize}
-\item a finite set of states
-\item \underline{some} these states are the start states
+\item a finite set of states, \bl{$Qs$}
+\item \underline{some} these states are the start states, \bl{$Qs_0$}
\item some states are accepting states, and
-\item there is transition \alert{relation}\medskip
+\item there is transition \alert{relation}, \bl{$\rho$}\medskip
\end{itemize}
@@ -366,7 +367,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Rexp to NFA}
+\frametitle{Thompson: Rexp to $\epsilon$NFA}
\begin{center}
\begin{tabular}[t]{l@{\hspace{10mm}}l}
@@ -597,6 +598,143 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
+\frametitle{\mbox{NFA Breadth-First: \boldmath{}$a^{?\{n\}}\!\cdot\! a^{\{n\}}$}}
+
+\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=6cm,
+ legend entries={Python,Ruby,my NFA},
+ 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=red}] table {nfabreadth.data};
+\end{axis}
+\end{tikzpicture}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+ \frametitle{NFA Breadth-First:\boldmath{}$(a^*)^* \cdot b$}
+
+\bigskip
+\begin{center}
+\begin{tikzpicture}
+ \begin{axis}[
+ xlabel={\pcode{a}s},
+ %%x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,10,...,100},
+ xmax=103,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=9cm,
+ height=6cm,
+ legend entries={Java 8,Python,JavaScript,Swift,Dart,my NFA},
+ legend pos=outer north east,
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
+\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
+
+\addplot[red,mark=triangle*, mark options={fill=red}] table {nfabreadth2.data};
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{NFA Depth-First: \boldmath$a^{?\{n\}} \cdot a^{\{n\}}$}
+
+\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=6cm,
+ legend entries={Python,Ruby,my NFA},
+ 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=red}] table {nfadepth.data};
+\end{axis}
+\end{tikzpicture}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+ \frametitle{NFA Depth-First: \boldmath$(a^*)^* \cdot b$}
+
+\bigskip
+\begin{center}
+\begin{tikzpicture}
+ \begin{axis}[
+ xlabel={\pcode{a}s},
+ %%x label style={at={(1.05,0.0)}},
+ ylabel={time in secs},
+ enlargelimits=false,
+ xtick={0,15,...,30},
+ xmax=33,
+ ymax=35,
+ ytick={0,5,...,30},
+ scaled ticks=false,
+ axis lines=left,
+ width=9cm,
+ height=6cm,
+ legend entries={Java 8,Python,JavaScript,Swift,Dart,my NFA},
+ legend pos=outer north east,
+ legend cell align=left]
+\addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
+\addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
+\addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data};
+\addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data};
+
+\addplot[red,mark=triangle*, mark options={fill=red}] table {nfadepth2.data};
+\end{axis}
+\end{tikzpicture}
+\end{center}
+
+The punchline is that many existing libraries do depth-first search
+in NFAs (with backtracking).
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
\frametitle{Subset Construction}
@@ -1275,36 +1413,6 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
-
-\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=10cm,
- height=7cm,
- legend entries={Python,Ruby,my NFA},
- 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 {nfasearch.data};
-\end{axis}
-\end{tikzpicture}
-
-The punchline is that many existing libraries do depth-first search
-in NFAs (backtracking).
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%