# HG changeset patch # User Christian Urban # Date 1602595750 -3600 # Node ID 5385c8342f020c3d1b96fbc28095242eb0452187 # Parent 3e5f5d19f514b7af956fa7fe56f0cfc54087d21c updated diff -r 3e5f5d19f514 -r 5385c8342f02 data.sty --- a/data.sty Sun Oct 11 09:10:08 2020 +0100 +++ b/data.sty Tue Oct 13 14:29:10 2020 +0100 @@ -353,7 +353,74 @@ 6500001 39.90294 7000001 53.50961 \end{filecontents} - + +% example a?{n} a{n} +\begin{filecontents}{nfabreadth.data} +1 0.00744 +2 0.02007 +3 0.07366 +4 0.13740 +5 0.21123 +6 0.42507 +7 0.70248 +8 1.54966 +9 2.88386 +10 5.01238 +11 9.87160 +12 19.25107 +13 38.60304 +\end{filecontents} + +% example (a*)* b +\begin{filecontents}{nfabreadth2.data} +1 0.01049 +6 0.05657 +11 0.08678 +16 0.13492 +21 0.25846 +26 0.28099 +31 0.35256 +36 0.35518 +41 0.36102 +46 0.42248 +51 0.54021 +56 0.64374 +61 0.61032 +66 0.65779 +71 0.79430 +76 0.79791 +81 0.79772 +86 0.85896 +91 1.00160 +96 1.11727 +\end{filecontents} + +% example a?{n} a{n} +\begin{filecontents}{nfadepth.data} +1 0.00047 +2 0.00485 +3 0.02597 +4 0.02026 +5 0.88002 +6 1.85384 +7 24.01612 +8 15.13296 +9 479.93808 +\end{filecontents} + +% example (a*)* b +\begin{filecontents}{nfadepth2.data} +1 0.00905 +2 0.04748 +3 0.17583 +4 1.00126 +5 3.19777 +6 13.37317 +7 55.52482 +\end{filecontents} + + + \begin{filecontents}{nfa.data} 0 0.00099 5 0.01304 diff -r 3e5f5d19f514 -r 5385c8342f02 progs/automata/enfa.sc --- a/progs/automata/enfa.sc Sun Oct 11 09:10:08 2020 +0100 +++ b/progs/automata/enfa.sc Tue Oct 13 14:29:10 2020 +0100 @@ -6,7 +6,7 @@ // a fixpoint construction import scala.annotation.tailrec @tailrec -def fixpT[A](f: A => A, x: A): A = { +def fixpT[S](f: S => S, x: S): S = { val fx = f(x) if (fx == x) x else fixpT(f, fx) } @@ -49,10 +49,11 @@ case (Q2, Some('b')) => Set(Q2) } -val enfa1 = eNFA(Set[State](Q0), enfa_trans1, Set[State](Q2)) +val nfa1 = + eNFA(Set[State](Q0), enfa_trans1, Set[State](Q2)) -// +// more examples case object R1 extends State case object R2 extends State case object R3 extends State @@ -64,4 +65,5 @@ } -val enfa2 = eNFA(Set[State](R1), enfa_trans1, Set[State](R3)) +val nfa2 = + eNFA(Set[State](R1), enfa_trans1, Set[State](R3)) diff -r 3e5f5d19f514 -r 5385c8342f02 progs/automata/thompson.sc --- 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)))) } diff -r 3e5f5d19f514 -r 5385c8342f02 slides/slides02.pdf Binary file slides/slides02.pdf has changed diff -r 3e5f5d19f514 -r 5385c8342f02 slides/slides03.pdf Binary file slides/slides03.pdf has changed 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} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%