diff -r 3e5f5d19f514 -r 5385c8342f02 slides/slides03.tex
--- 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}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
 
 
 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%