--- a/progs/automata/thompson.sc Sun Oct 11 09:10:08 2020 +0100
+++ b/progs/automata/thompson.sc Tue Oct 13 14:29:10 2020 +0100
@@ -55,33 +55,33 @@
// sequence of two NFAs
-def NFA_SEQ(enfa1: NFAt, enfa2: NFAt) : NFAt = {
+def NFA_SEQ(nfa1: NFAt, nfa2: NFAt) : NFAt = {
val new_delta : eNFAtrans =
- { case (q, None) if enfa1.fins(q) => enfa2.starts }
+ { case (q, None) if nfa1.fins(q) => nfa2.starts }
- eNFA(enfa1.starts,
- new_delta +++ enfa1.delta +++ enfa2.delta,
- enfa2.fins)
+ eNFA(nfa1.starts,
+ new_delta +++ nfa1.delta +++ nfa2.delta,
+ nfa2.fins)
}
// alternative of two NFAs
-def NFA_ALT(enfa1: NFAt, enfa2: NFAt) : NFAt = {
+def NFA_ALT(nfa1: NFAt, nfa2: NFAt) : NFAt = {
val new_delta : NFAtrans = {
- case (q, c) => applyOrElse(enfa1.delta, (q, c)) |
- applyOrElse(enfa2.delta, (q, c)) }
- val new_fins = (q: TState) => enfa1.fins(q) || enfa2.fins(q)
+ case (q, c) => applyOrElse(nfa1.delta, (q, c)) |
+ applyOrElse(nfa2.delta, (q, c)) }
+ val new_fins = (q: TState) => nfa1.fins(q) || nfa2.fins(q)
- NFA(enfa1.starts | enfa2.starts, new_delta, new_fins)
+ NFA(nfa1.starts | nfa2.starts, new_delta, new_fins)
}
// star of a NFA
-def NFA_STAR(enfa: NFAt) : NFAt = {
+def NFA_STAR(nfa: NFAt) : NFAt = {
val Q = TState()
val new_delta : eNFAtrans =
- { case (Q, None) => enfa.starts
- case (q, None) if enfa.fins(q) => Set(Q) }
+ { case (Q, None) => nfa.starts
+ case (q, None) if nfa.fins(q) => Set(Q) }
- eNFA(Set(Q), new_delta +++ enfa.delta, Set(Q))
+ eNFA(Set(Q), new_delta +++ nfa.delta, Set(Q))
}
@@ -147,6 +147,7 @@
// the size of the NFA can be large,
// thus slowing down the breadth-first search
+println("Breadth-first search EVIL1 / EVIL2")
for (i <- 1 to 13) {
println(i + ": " + "%.5f".format(time_needed(2, tmatches_nfa(EVIL1(i), "a" * i))))
@@ -159,8 +160,13 @@
// the backtracking that is needed in depth-first
// search can be painfully slow
+println("Depth-first search EVIL1 / EVIL2")
-for (i <- 1 to 8) {
+for (i <- 1 to 9) {
+ println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL1(i), "a" * i))))
+}
+
+for (i <- 1 to 7) {
println(i + " " + "%.5f".format(time_needed(2, tmatches_nfa2(EVIL2, "a" * i))))
}
--- 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}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%