49 An Efficient Regular\\[-1mm] |
49 An Efficient Regular\\[-1mm] |
50 Expression Matcher\end{tabular}} |
50 Expression Matcher\end{tabular}} |
51 |
51 |
52 \footnotesize |
52 \footnotesize |
53 \begin{center} |
53 \begin{center} |
54 {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\\ |
54 {\normalsize Graphs: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} and strings \bl{$\underbrace{\,a\ldots a\,}_{n}$}}\smallskip\\ |
55 \begin{tabular}{@{}cc@{}} |
55 \begin{tabular}{@{}cc@{}} |
56 \begin{tikzpicture} |
56 \begin{tikzpicture} |
57 \begin{axis}[ |
57 \begin{axis}[ |
58 xlabel={$n$}, |
58 xlabel={$n$}, |
59 x label style={at={(1.05,0.0)}}, |
59 x label style={at={(1.05,0.0)}}, |
67 axis lines=left, |
67 axis lines=left, |
68 width=5cm, |
68 width=5cm, |
69 height=4.5cm, |
69 height=4.5cm, |
70 legend entries={Python,Ruby}, |
70 legend entries={Python,Ruby}, |
71 legend pos=north west, |
71 legend pos=north west, |
72 legend cell align=left |
72 legend cell align=left] |
73 ] |
|
74 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
73 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
75 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
74 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
76 \end{axis} |
75 \end{axis} |
77 \end{tikzpicture} |
76 \end{tikzpicture} |
78 & |
77 & |
87 ymax=35, |
86 ymax=35, |
88 ytick={0,5,...,30}, |
87 ytick={0,5,...,30}, |
89 scaled ticks=false, |
88 scaled ticks=false, |
90 axis lines=left, |
89 axis lines=left, |
91 width=5cm, |
90 width=5cm, |
92 height=4.5cm |
91 height=4.5cm, |
93 ] |
92 legend entries={Scala V2,Scala V3}, |
|
93 legend pos=north west, |
|
94 legend cell align=left] |
94 \addplot[green,mark=square*,mark options={fill=white}] table {re2.data}; |
95 \addplot[green,mark=square*,mark options={fill=white}] table {re2.data}; |
95 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
96 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
96 \end{axis} |
97 \end{axis} |
97 \end{tikzpicture} |
98 \end{tikzpicture} |
98 \end{tabular} |
99 \end{tabular} |
99 \end{center} |
100 \end{center} |
100 |
101 |
101 \small |
102 \small |
102 In the handouts is a similar graph with \bl{$(a^*)^* \cdot b$} for Java. |
103 In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java. |
103 |
104 |
104 \end{frame} |
105 \end{frame} |
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
106 |
107 |
107 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
173 \end{center}\bigskip |
174 \end{center}\bigskip |
174 |
175 |
175 \item[] For example |
176 \item[] For example |
176 |
177 |
177 \begin{center} |
178 \begin{center} |
178 \begin{tabular}{lcll} |
179 \begin{tabular}{lcl@{\hspace{10mm}}l} |
179 \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(\{[]\})$}\\ |
180 \bl{$A^4$} & \bl{$=$} & \bl{$A \,@\, A \,@\, A \,@\, A$} & \bl{$(@\,\{[]\})$}\\ |
180 \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(\{[]\})$}\\ |
181 \bl{$A^1$} & \bl{$=$} & \bl{$A$} & \bl{$(@\,\{[]\})$}\\ |
181 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ |
182 \bl{$A^0$} & \bl{$=$} & \bl{$\{[]\}$}\\ |
182 \end{tabular} |
183 \end{tabular} |
183 \end{center} |
184 \end{center} |
184 |
185 |
185 \end{itemize} |
186 \end{itemize} |
255 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ |
256 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ |
256 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ |
257 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ |
257 \end{tabular} |
258 \end{tabular} |
258 \end{textblock} |
259 \end{textblock} |
259 |
260 |
260 \begin{textblock}{6}(9,12)\small |
261 \begin{textblock}{9}(6,12)\small |
261 \bl{$L$} is a function from regular expressions to |
262 \bl{$L$} is a function from regular expressions to |
262 sets of strings\\ |
263 sets of strings (languages):\smallskip\\ |
263 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
264 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
264 \end{textblock} |
265 \end{textblock} |
265 |
266 |
266 \end{frame} |
267 \end{frame} |
267 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
268 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
330 Their inductive definition: |
331 Their inductive definition: |
331 |
332 |
332 |
333 |
333 \begin{textblock}{6}(2,7.5) |
334 \begin{textblock}{6}(2,7.5) |
334 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
335 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
335 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & null\\ |
336 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ |
336 & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ |
337 & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ |
337 & \bl{$\mid$} & \bl{$c$} & character\\ |
338 & \bl{$\mid$} & \bl{$c$} & single character\\ |
338 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
339 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
339 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
340 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
340 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
341 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
341 \end{tabular} |
342 \end{tabular} |
342 \end{textblock} |
343 \end{textblock} |
744 |
746 |
745 \end{frame} |
747 \end{frame} |
746 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
748 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
747 |
749 |
748 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
750 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
751 %\begin{frame}[c] |
|
752 %\frametitle{\bl{$(a^*)^* \cdot b$}} |
|
753 % |
|
754 %\begin{center} |
|
755 %\begin{tikzpicture} |
|
756 % \begin{axis}[ |
|
757 % xlabel={$n$}, |
|
758 % x label style={at={(1.09,0.0)}}, |
|
759 % ylabel={time in secs}, |
|
760 % enlargelimits=false, |
|
761 % xmax=27, |
|
762 % xtick={0,5,...,20}, |
|
763 % ytick={0,5,...,25}, |
|
764 % ymax=13, |
|
765 % scaled ticks=false, |
|
766 % axis lines=left, |
|
767 % width=9cm, |
|
768 % height=5cm, |
|
769 % legend entries={Scala V2}, |
|
770 % legend pos=north west, |
|
771 % legend cell align=left] |
|
772 %\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data}; |
|
773 %% still needs to be done |
|
774 %%\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; |
|
775 %\end{axis} |
|
776 %\end{tikzpicture} |
|
777 %\end{center} |
|
778 % |
|
779 %\end{frame} |
|
780 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
781 |
|
782 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
749 \begin{frame}[c] |
783 \begin{frame}[c] |
750 \frametitle{\bl{$(a^*)^* \cdot b$}} |
784 \frametitle{\bl{$(a^*)^* \cdot b$}} |
751 |
785 |
752 \begin{center} |
786 \begin{center} |
753 \begin{tikzpicture} |
787 \begin{tikzpicture} |
754 \begin{axis}[ |
788 \begin{axis}[ |
755 xlabel={$n$}, |
789 xlabel={$n$}, |
756 x label style={at={(1.09,0.0)}}, |
790 x label style={at={(1.09,0.0)}}, |
757 ylabel={time in secs}, |
791 ylabel={time in secs}, |
758 enlargelimits=false, |
792 enlargelimits=false, |
759 xmax=27, |
793 ytick={0,10,...,30}, |
760 xtick={0,5,...,20}, |
794 ymax=35, |
761 ytick={0,5,...,25}, |
|
762 ymax=13, |
|
763 scaled ticks=false, |
|
764 axis lines=left, |
|
765 width=9cm, |
|
766 height=5cm, |
|
767 legend entries={Scala V2}, |
|
768 legend pos=north west, |
|
769 legend cell align=left] |
|
770 \addplot[green,mark=square*,mark options={fill=white}] table {re2a.data}; |
|
771 %% still needs to be done |
|
772 %%\addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; |
|
773 \end{axis} |
|
774 \end{tikzpicture} |
|
775 \end{center} |
|
776 |
|
777 \end{frame} |
|
778 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
779 |
|
780 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
781 \begin{frame}[c] |
|
782 \frametitle{\bl{$(a^*)^* \cdot b$}} |
|
783 |
|
784 \begin{center} |
|
785 \begin{tikzpicture} |
|
786 \begin{axis}[ |
|
787 xlabel={$n$}, |
|
788 x label style={at={(1.09,0.0)}}, |
|
789 ylabel={time in secs}, |
|
790 enlargelimits=false, |
|
791 ytick={0,10,...,60}, |
|
792 ymax=65, |
|
793 axis lines=left, |
795 axis lines=left, |
794 width=9cm, |
796 width=9cm, |
795 height=5cm, |
797 height=5cm, |
796 legend entries={Scala V3}, |
798 legend entries={Scala V3}, |
797 legend pos=north west, |
799 legend pos=north east, |
798 legend cell align=left] |
800 legend cell align=left] |
799 \addplot[green,mark=square*,mark options={fill=white}] table {re2a.data}; |
801 %\addplot[green,mark=square*,mark options={fill=white}] table {re2a.data}; |
800 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; |
802 \addplot[black,mark=square*,mark options={fill=white}] table {re3a.data}; |
801 \end{axis} |
803 \end{axis} |
802 \end{tikzpicture} |
804 \end{tikzpicture} |
803 \end{center} |
805 \end{center} |
804 |
806 |