58 \end{textblock} |
58 \end{textblock} |
59 \begin{textblock}{6}(8,8.5) |
59 \begin{textblock}{6}(8,8.5) |
60 \includegraphics[scale=0.2]{../pics/s2.png} |
60 \includegraphics[scale=0.2]{../pics/s2.png} |
61 \end{textblock}} |
61 \end{textblock}} |
62 |
62 |
63 \only<4>{ |
63 \only<4->{ |
64 \begin{textblock}{6}(0.6,8.5) |
64 \begin{textblock}{6}(0.6,8.5) |
65 \includegraphics[scale=0.2]{../pics/s3.png} |
65 \includegraphics[scale=0.2]{../pics/s3.png} |
66 \end{textblock} |
66 \end{textblock} |
67 \begin{textblock}{6}(8,8.5) |
67 \begin{textblock}{6}(8,8.5) |
68 \includegraphics[scale=0.2]{../pics/s4.png} |
68 \includegraphics[scale=0.2]{../pics/s4.png} |
|
69 \end{textblock}} |
|
70 |
|
71 \only<5>{ |
|
72 \begin{textblock}{6}(1.5,14.5) |
|
73 room too hot, 3h lecture |
69 \end{textblock}} |
74 \end{textblock}} |
70 |
75 |
71 % \begin{itemize} |
76 % \begin{itemize} |
72 % \item {\bf My Voice} ``lecturer speaks in a low voice and |
77 % \item {\bf My Voice} ``lecturer speaks in a low voice and |
73 % is hard to hear him'' ``please use mic'' ``please use mic |
78 % is hard to hear him'' ``please use mic'' ``please use mic |
121 |
126 |
122 \only<2-6>{\small |
127 \only<2-6>{\small |
123 \begin{textblock}{6}(1,0.8) |
128 \begin{textblock}{6}(1,0.8) |
124 \begin{bubble}[6.7cm] |
129 \begin{bubble}[6.7cm] |
125 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
130 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
126 \multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} + \bl{$\mbox{Q}_2$}:}\\ |
131 \multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} \& \bl{$\mbox{Q}_2$}:}\\ |
127 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ |
132 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ |
128 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} |
133 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} |
129 \end{tabular} |
134 \end{tabular} |
130 \end{bubble} |
135 \end{bubble} |
131 \end{textblock}} |
136 \end{textblock}} |
236 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
241 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
237 \addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; |
242 \addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; |
238 \end{axis} |
243 \end{axis} |
239 \end{tikzpicture} |
244 \end{tikzpicture} |
240 |
245 |
241 The punchline is that existing libraries do depth-first search in NFAs. |
246 The punchline is that many existing libraries do depth-first search |
|
247 in NFAs (backtracking). |
242 |
248 |
243 \end{frame} |
249 \end{frame} |
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
250 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
245 |
251 |
246 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
252 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
765 \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ |
778 \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ |
766 \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ |
779 \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ |
767 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
780 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
768 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
781 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
769 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ |
782 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ |
770 \bl{$inj\,(r^*)\,c\,(Seq(v,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\ |
783 \bl{$inj\,(r^*)\,c\,(Seq(v,Stars\,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\ |
771 \end{tabular} |
784 \end{tabular} |
772 \end{center}\bigskip |
785 \end{center}\bigskip |
773 |
786 |
774 \footnotesize |
787 \footnotesize |
775 \bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value |
788 \bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value |