239 \begin{frame}[c] |
239 \begin{frame}[c] |
240 \frametitle{\begin{tabular}{c} |
240 \frametitle{\begin{tabular}{c} |
241 Non-Deterministic\\[-1mm] |
241 Non-Deterministic\\[-1mm] |
242 Finite Automata\end{tabular}} |
242 Finite Automata\end{tabular}} |
243 |
243 |
244 A non-deterministic finite automaton (NFA) consists again of: |
244 \bl{$N(\varSigma, \mbox{Qs}, \mbox{Qs}_0, F, \rho)$}\\ |
|
245 A non-deterministic finite automaton (NFA) consists of: |
245 |
246 |
246 \begin{itemize} |
247 \begin{itemize} |
247 \item a finite set of states |
248 \item a finite set of states, \bl{$Qs$} |
248 \item \underline{some} these states are the start states |
249 \item \underline{some} these states are the start states, \bl{$Qs_0$} |
249 \item some states are accepting states, and |
250 \item some states are accepting states, and |
250 \item there is transition \alert{relation}\medskip |
251 \item there is transition \alert{relation}, \bl{$\rho$}\medskip |
251 \end{itemize} |
252 \end{itemize} |
252 |
253 |
253 |
254 |
254 \begin{center} |
255 \begin{center} |
255 \begin{tabular}{c} |
256 \begin{tabular}{c} |
364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
365 |
366 |
366 |
367 |
367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
368 \begin{frame}[c] |
369 \begin{frame}[c] |
369 \frametitle{Rexp to NFA} |
370 \frametitle{Thompson: Rexp to $\epsilon$NFA} |
370 |
371 |
371 \begin{center} |
372 \begin{center} |
372 \begin{tabular}[t]{l@{\hspace{10mm}}l} |
373 \begin{tabular}[t]{l@{\hspace{10mm}}l} |
373 \raisebox{1mm}{\bl{$\ZERO$}} & |
374 \raisebox{1mm}{\bl{$\ZERO$}} & |
374 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
375 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
595 \end{frame} |
596 \end{frame} |
596 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
597 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
597 |
598 |
598 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
599 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
599 \begin{frame}[c] |
600 \begin{frame}[c] |
|
601 \frametitle{\mbox{NFA Breadth-First: \boldmath{}$a^{?\{n\}}\!\cdot\! a^{\{n\}}$}} |
|
602 |
|
603 \begin{tikzpicture} |
|
604 \begin{axis}[xlabel={\pcode{a}s}, |
|
605 ylabel={time in secs}, |
|
606 enlargelimits=false, |
|
607 xtick={0,5,...,30}, |
|
608 xmax=30, |
|
609 ymax=35, |
|
610 ytick={0,5,...,30}, |
|
611 scaled ticks=false, |
|
612 axis lines=left, |
|
613 width=9cm, |
|
614 height=6cm, |
|
615 legend entries={Python,Ruby,my NFA}, |
|
616 legend pos=outer north east, |
|
617 legend cell align=left] |
|
618 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
|
619 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
|
620 \addplot[red,mark=triangle*, mark options={fill=red}] table {nfabreadth.data}; |
|
621 \end{axis} |
|
622 \end{tikzpicture} |
|
623 |
|
624 \end{frame} |
|
625 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
626 |
|
627 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
628 \begin{frame}[c] |
|
629 \frametitle{NFA Breadth-First:\boldmath{}$(a^*)^* \cdot b$} |
|
630 |
|
631 \bigskip |
|
632 \begin{center} |
|
633 \begin{tikzpicture} |
|
634 \begin{axis}[ |
|
635 xlabel={\pcode{a}s}, |
|
636 %%x label style={at={(1.05,0.0)}}, |
|
637 ylabel={time in secs}, |
|
638 enlargelimits=false, |
|
639 xtick={0,10,...,100}, |
|
640 xmax=103, |
|
641 ymax=35, |
|
642 ytick={0,5,...,30}, |
|
643 scaled ticks=false, |
|
644 axis lines=left, |
|
645 width=9cm, |
|
646 height=6cm, |
|
647 legend entries={Java 8,Python,JavaScript,Swift,Dart,my NFA}, |
|
648 legend pos=outer north east, |
|
649 legend cell align=left] |
|
650 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; |
|
651 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
|
652 \addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; |
|
653 \addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data}; |
|
654 \addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data}; |
|
655 |
|
656 \addplot[red,mark=triangle*, mark options={fill=red}] table {nfabreadth2.data}; |
|
657 \end{axis} |
|
658 \end{tikzpicture} |
|
659 \end{center} |
|
660 |
|
661 |
|
662 \end{frame} |
|
663 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
664 |
|
665 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
666 \begin{frame}[c] |
|
667 \frametitle{NFA Depth-First: \boldmath$a^{?\{n\}} \cdot a^{\{n\}}$} |
|
668 |
|
669 \begin{tikzpicture} |
|
670 \begin{axis}[xlabel={\pcode{a}s}, |
|
671 ylabel={time in secs}, |
|
672 enlargelimits=false, |
|
673 xtick={0,5,...,30}, |
|
674 xmax=30, |
|
675 ymax=35, |
|
676 ytick={0,5,...,30}, |
|
677 scaled ticks=false, |
|
678 axis lines=left, |
|
679 width=9cm, |
|
680 height=6cm, |
|
681 legend entries={Python,Ruby,my NFA}, |
|
682 legend pos=outer north east, |
|
683 legend cell align=left] |
|
684 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
|
685 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
|
686 \addplot[red,mark=triangle*, mark options={fill=red}] table {nfadepth.data}; |
|
687 \end{axis} |
|
688 \end{tikzpicture} |
|
689 |
|
690 \end{frame} |
|
691 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
692 |
|
693 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
694 \begin{frame}[c] |
|
695 \frametitle{NFA Depth-First: \boldmath$(a^*)^* \cdot b$} |
|
696 |
|
697 \bigskip |
|
698 \begin{center} |
|
699 \begin{tikzpicture} |
|
700 \begin{axis}[ |
|
701 xlabel={\pcode{a}s}, |
|
702 %%x label style={at={(1.05,0.0)}}, |
|
703 ylabel={time in secs}, |
|
704 enlargelimits=false, |
|
705 xtick={0,15,...,30}, |
|
706 xmax=33, |
|
707 ymax=35, |
|
708 ytick={0,5,...,30}, |
|
709 scaled ticks=false, |
|
710 axis lines=left, |
|
711 width=9cm, |
|
712 height=6cm, |
|
713 legend entries={Java 8,Python,JavaScript,Swift,Dart,my NFA}, |
|
714 legend pos=outer north east, |
|
715 legend cell align=left] |
|
716 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data}; |
|
717 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
|
718 \addplot[red,mark=*, mark options={fill=white}] table {re-js.data}; |
|
719 \addplot[magenta,mark=*, mark options={fill=white}] table {re-swift.data}; |
|
720 \addplot[brown,mark=*, mark options={fill=white}] table {re-dart.data}; |
|
721 |
|
722 \addplot[red,mark=triangle*, mark options={fill=red}] table {nfadepth2.data}; |
|
723 \end{axis} |
|
724 \end{tikzpicture} |
|
725 \end{center} |
|
726 |
|
727 The punchline is that many existing libraries do depth-first search |
|
728 in NFAs (with backtracking). |
|
729 |
|
730 \end{frame} |
|
731 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
732 |
|
733 |
|
734 |
|
735 |
|
736 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
737 \begin{frame}[c] |
600 \frametitle{Subset Construction} |
738 \frametitle{Subset Construction} |
601 |
739 |
602 |
740 |
603 \begin{textblock}{5}(1,1.5) |
741 \begin{textblock}{5}(1,1.5) |
604 \begin{center} |
742 \begin{center} |
1273 |
1411 |
1274 \end{frame} |
1412 \end{frame} |
1275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1413 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1276 |
1414 |
1277 |
1415 |
1278 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1279 \begin{frame}[t] |
|
1280 \frametitle{\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}} |
|
1281 |
|
1282 \begin{tikzpicture} |
|
1283 \begin{axis}[xlabel={\pcode{a}s},ylabel={time in secs}, |
|
1284 enlargelimits=false, |
|
1285 xtick={0,5,...,30}, |
|
1286 xmax=30, |
|
1287 ymax=35, |
|
1288 ytick={0,5,...,30}, |
|
1289 scaled ticks=false, |
|
1290 axis lines=left, |
|
1291 width=10cm, |
|
1292 height=7cm, |
|
1293 legend entries={Python,Ruby,my NFA}, |
|
1294 legend pos=north west, |
|
1295 legend cell align=left] |
|
1296 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
|
1297 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
|
1298 \addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; |
|
1299 \end{axis} |
|
1300 \end{tikzpicture} |
|
1301 |
|
1302 The punchline is that many existing libraries do depth-first search |
|
1303 in NFAs (backtracking). |
|
1304 |
|
1305 \end{frame} |
|
1306 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1307 |
|
1308 |
1416 |
1309 |
1417 |
1310 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1418 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1311 % \begin{frame}[c] |
1419 % \begin{frame}[c] |
1312 % \frametitle{DFA to Rexp} |
1420 % \frametitle{DFA to Rexp} |