41 \end{frame} |
43 \end{frame} |
42 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
43 |
45 |
44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
46 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
45 \begin{frame}[c] |
47 \begin{frame}[c] |
|
48 \frametitle{\begin{tabular}{@ {}c@ {}}An Efficient Regular\\[-1mm] |
|
49 Expression Matcher\end{tabular}} |
|
50 |
|
51 \footnotesize |
|
52 \begin{center} |
|
53 \begin{tabular}{@{}cc@{}} |
|
54 \begin{tikzpicture} |
|
55 \begin{axis}[ |
|
56 xlabel={\pcode{a}s}, |
|
57 ylabel={time in secs}, |
|
58 enlargelimits=false, |
|
59 xtick={0,5,...,30}, |
|
60 xmax=30, |
|
61 ymax=35, |
|
62 ytick={0,5,...,30}, |
|
63 scaled ticks=false, |
|
64 axis lines=left, |
|
65 width=4.5cm, |
|
66 height=4.5cm, |
|
67 legend entries={Python,Ruby}, |
|
68 legend pos=north west, |
|
69 legend cell align=left |
|
70 ] |
|
71 \addplot[blue,mark=*, mark options={fill=white}] |
|
72 table {re-python.data}; |
|
73 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
|
74 table {re-ruby.data}; |
|
75 \end{axis} |
|
76 \end{tikzpicture} |
|
77 & |
|
78 \begin{tikzpicture} |
|
79 \begin{axis}[ |
|
80 xlabel={\pcode{a}s}, |
|
81 ylabel={time in secs}, |
|
82 enlargelimits=false, |
|
83 xtick={0,3000,...,12000}, |
|
84 xmax=12000, |
|
85 ymax=35, |
|
86 ytick={0,5,...,30}, |
|
87 scaled ticks=false, |
|
88 axis lines=left, |
|
89 width=5.5cm, |
|
90 height=4.5cm |
|
91 ] |
|
92 \addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; |
|
93 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
|
94 \end{axis} |
|
95 \end{tikzpicture} |
|
96 \end{tabular} |
|
97 \end{center} |
|
98 |
|
99 |
|
100 \end{frame} |
|
101 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
102 |
|
103 |
|
104 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
105 \begin{frame}[c] |
46 \frametitle{Languages, Strings} |
106 \frametitle{Languages, Strings} |
47 |
107 |
48 \begin{itemize} |
108 \begin{itemize} |
49 \item A \alert{language} is a set of strings.\medskip |
109 \item \alert{\bf Strings} are lists of characters, for example |
50 \begin{center} |
110 \begin{center} |
51 \bl{\{[], hello, foobar, a, abc\}} |
111 \bl{$[]$},\;\bl{$abc$} \hspace{2cm}(Pattern match: \bl{$c\!::\!s$}) |
52 \end{center}\bigskip |
112 \end{center}\bigskip |
53 |
113 |
54 \item The \alert{meaning} of a regular expression is a set of |
114 |
55 strings, or language. |
115 \item A \alert{\bf language} is a set of strings, for example\medskip |
|
116 \begin{center} |
|
117 \bl{$\{[], hello, \textit{foobar}, a, abc\}$} |
|
118 \end{center}\bigskip |
|
119 |
|
120 \item \alert{\bf Concatenation} of strings and sets |
|
121 |
|
122 \begin{center} |
|
123 \begin{tabular}{rcl} |
|
124 \bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\ |
|
125 \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} |
|
126 \end{tabular} |
|
127 \end{center} |
|
128 |
|
129 %\item The \alert{\bf meaning} of a regular expression is a set of |
|
130 % strings, or language. |
56 \end{itemize} |
131 \end{itemize} |
57 |
132 |
58 \end{frame} |
133 \end{frame} |
59 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
60 |
135 |
61 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
136 |
62 \mode<presentation>{ |
137 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
63 \begin{frame}[t] |
|
64 \frametitle{\begin{tabular}{c}Strings\end{tabular}} |
|
65 |
|
66 Different ways of writing strings: |
|
67 |
|
68 \begin{center} |
|
69 \begin{tabular}{ccc} |
|
70 \bl{\consolas"$hello$"}\quad{} & \bl{$[h, e, l, l, o]$} & \quad\bl{$h\!::\!e\!::\!l\!::\!l\!::\!o\!::\!N\!il$}\bigskip\\ |
|
71 \bl{\consolas ""} & \bl{$[]$} & \bl{$N$\!$il$} |
|
72 \end{tabular} |
|
73 \end{center}\pause |
|
74 |
|
75 The concatenation operation on strings and sets of strings: |
|
76 |
|
77 \begin{center} |
|
78 \begin{tabular}{l} |
|
79 \bl{{\consolas"$f\!oo$"}$\;@\;${\consolas"$bar$"}$\;=\;${\consolas"$f\!oobar$"}}\medskip\\ |
|
80 \bl{$A \;@\; B \dn \{ s_1 @ s_2 \mid s_1 \in A \wedge s_2 \in B\}$} |
|
81 \end{tabular} |
|
82 \end{center} |
|
83 |
|
84 \end{frame}} |
|
85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
86 |
|
87 |
|
88 |
|
89 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
90 \mode<presentation>{ |
|
91 \begin{frame}[t] |
138 \begin{frame}[t] |
92 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
139 \frametitle{\begin{tabular}{c}Regular Expressions\end{tabular}} |
93 |
140 |
94 Their inductive definition: |
141 Their inductive definition: |
95 |
142 |
96 |
143 |
97 \begin{textblock}{6}(2,6.5) |
144 \begin{textblock}{6}(2,7.5) |
98 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
145 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
99 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
146 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$} & null\\ |
100 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / {\consolas""} / $[]$\\ |
147 & \bl{$\mid$} & \bl{$\epsilon$} & empty string / \pcode{""} / $[]$\\ |
101 & \bl{$\mid$} & \bl{$c$} & character\\ |
148 & \bl{$\mid$} & \bl{$c$} & character\\ |
102 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
149 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
103 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
150 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
104 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
151 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
105 \end{tabular} |
152 \end{tabular} |
106 \end{textblock} |
153 \end{textblock} |
107 |
154 |
108 |
155 |
109 \only<2->{ |
156 \only<2->{\footnotesize |
110 \begin{textblock}{9}(4,0.5) |
157 \begin{textblock}{9}(2,0.5) |
111 \begin{tikzpicture} |
158 \begin{bubble}[9.8cm] |
112 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] |
159 \lstinputlisting{../progs/app01.scala} |
113 {\normalsize\color{darkgray} |
160 \end{bubble} |
114 \begin{minipage}{9cm} |
|
115 \hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
116 \texttt{\lstinputlisting{../progs/app51.scala}}}} |
|
117 \end{minipage}}; |
|
118 \end{tikzpicture} |
|
119 \end{textblock}} |
161 \end{textblock}} |
120 |
162 |
121 \end{frame}} |
163 \end{frame} |
122 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
123 |
165 |
124 |
166 |
125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
167 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
126 \mode<presentation>{ |
|
127 \begin{frame}[c] |
168 \begin{frame}[c] |
128 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} |
169 \frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} |
129 |
170 |
130 \begin{textblock}{15}(1,4) |
171 \begin{textblock}{15}(1,4) |
131 \begin{tabular}{@ {}rcl} |
172 \begin{tabular}{@ {}rcl} |
132 \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\ |
173 \bl{$L(\varnothing)$} & \bl{$\dn$} & \bl{$\varnothing$}\\ |
133 \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{$""$\}$}\\ |
174 \bl{$L(\epsilon)$} & \bl{$\dn$} & \bl{$\{$[]$\}$}\\ |
134 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{"c"\}$}\\ |
175 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
135 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
176 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
136 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
177 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
137 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0} L(r)^n$}\\ |
178 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$\bigcup_{n \ge 0} L(r)^n$}\\ |
138 \end{tabular}\bigskip |
179 \end{tabular}\bigskip |
139 |
180 |
140 \only<2->{ |
181 \only<2->{ |
141 \hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{""\}$}\\ |
182 \hspace{5mm}\textcolor{blue}{$L(r)^0 \;\dn\; \{[]\}$}\\ |
142 \textcolor{blue}{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}} |
183 \textcolor{blue}{$L(r)^{n+1} \;\dn\; L(r) \,@\, L(r)^n$}} |
143 \end{textblock} |
184 \end{textblock} |
144 |
|
145 |
|
146 |
185 |
147 \only<1->{ |
186 \only<1->{ |
148 \begin{textblock}{6}(9,12)\small |
187 \begin{textblock}{6}(9,12)\small |
149 \bl{$L$} is a function from regular expressions to sets of strings\\ |
188 \bl{$L$} is a function from regular expressions to sets of strings\\ |
150 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
189 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
151 \end{textblock}} |
190 \end{textblock}} |
152 |
191 |
153 |
192 \end{frame} |
154 \end{frame}} |
193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
194 |
156 |
195 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
157 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
158 \mode<presentation>{ |
|
159 \begin{frame}[c] |
196 \begin{frame}[c] |
160 |
197 |
161 \large |
198 \large |
162 \begin{center} |
199 \begin{center} |
163 What is \bl{$L(a^*)$}? |
200 What is \bl{$L(a^*)$}? |
164 \end{center} |
201 \end{center} |
165 |
202 |
166 \end{frame}} |
203 \end{frame} |
167 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
204 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
168 |
205 |
169 |
206 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
207 \begin{frame}[t] |
|
208 \frametitle{\begin{tabular}{c}Concrete Equivalences\end{tabular}} |
|
209 |
|
210 \begin{center} |
|
211 \bl{\begin{tabular}{rcl} |
|
212 $(a + b) + c$ & $\equiv$ & $a + (b + c)$\\ |
|
213 $a + a$ & $\equiv$ & $a$\\ |
|
214 $a + b$ & $\equiv$ & $b + a$\\ |
|
215 $(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\ |
|
216 $c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause |
|
217 $a \cdot a$ & $\not\equiv$ & $a$\\ |
|
218 $a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\ |
|
219 \end{tabular}} |
|
220 \end{center} |
|
221 |
|
222 \end{frame} |
|
223 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
224 |
|
225 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
226 \begin{frame}[t] |
|
227 \frametitle{\begin{tabular}{c}Corner Cases\end{tabular}} |
|
228 |
|
229 \begin{center} |
|
230 \bl{\begin{tabular}{rcl} |
|
231 $a \cdot \varnothing$ & $\not\equiv$ & $a$\\ |
|
232 $a + \epsilon$ & $\not\equiv$ & $a$\\ |
|
233 $\epsilon$ & $\equiv$ & $\varnothing^*$\\ |
|
234 $\epsilon^*$ & $\equiv$ & $\epsilon$\\ |
|
235 $\varnothing^*$ & $\not\equiv$ & $\varnothing$\\ |
|
236 \end{tabular}} |
|
237 \end{center} |
|
238 |
|
239 \end{frame} |
|
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
241 |
|
242 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
243 \begin{frame}[t] |
|
244 \frametitle{\begin{tabular}{c}Simplification Rules\end{tabular}} |
|
245 |
|
246 \begin{center} |
|
247 \bl{\begin{tabular}{rcl} |
|
248 $r + \varnothing$ & $\equiv$ & $r$\\ |
|
249 $\varnothing + r$ & $\equiv$ & $r$\\ |
|
250 $r \cdot \epsilon$ & $\equiv$ & $r$\\ |
|
251 $\epsilon \cdot r$ & $\equiv$ & $r$\\ |
|
252 $r \cdot \varnothing$ & $\equiv$ & $\varnothing$\\ |
|
253 $\varnothing \cdot r$ & $\equiv$ & $\varnothing$\\ |
|
254 $r + r$ & $\equiv$ & $r$ |
|
255 \end{tabular}} |
|
256 \end{center} |
|
257 |
|
258 \end{frame} |
|
259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
170 |
260 |
171 \newcommand{\YES}{\textcolor{gray}{yes}} |
261 \newcommand{\YES}{\textcolor{gray}{yes}} |
172 \newcommand{\NO}{\textcolor{gray}{no}} |
262 \newcommand{\NO}{\textcolor{gray}{no}} |
173 \newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}} |
263 \newcommand{\FORALLR}{\textcolor{gray}{$\forall$ r.}} |
174 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
264 |
175 \mode<presentation>{ |
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
176 \begin{frame}[c] |
|
177 \frametitle{\begin{tabular}{c}Reg Exp Equivalences\end{tabular}} |
|
178 |
|
179 \begin{center} |
|
180 \begin{tabular}{l@ {\hspace{7mm}}rcl@ {\hspace{7mm}}l} |
|
181 &\bl{$(a + b) + c$} & \bl{$\equiv^?$} & \bl{$a + (b + c)$} & \onslide<2->{\YES}\\ |
|
182 &\bl{$a + a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<3->{\YES}\\ |
|
183 &\bl{$(a \cdot b) \cdot c$} & \bl{$\equiv^?$} & \bl{$a \cdot (b \cdot c)$} & \onslide<4->{\YES}\\ |
|
184 &\bl{$a \cdot a$} & \bl{$\equiv^?$} & \bl{$a$} & \onslide<5->{\NO}\\ |
|
185 &\bl{$\epsilon^*$} & \bl{$\equiv^?$} & \bl{$\epsilon$} & \onslide<6->{\YES}\\ |
|
186 &\bl{$\varnothing^*$} & \bl{$\equiv^?$} & \bl{$\varnothing$} & \onslide<7->{\NO}\\ |
|
187 \FORALLR &\bl{$r \cdot \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<8->{\YES}\\ |
|
188 \FORALLR &\bl{$r + \epsilon$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<9->{\NO}\\ |
|
189 \FORALLR &\bl{$r + \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<10->{\YES}\\ |
|
190 \FORALLR &\bl{$r \cdot \varnothing$} & \bl{$\equiv^?$} & \bl{$r$} & \onslide<11->{\NO}\\ |
|
191 &\bl{$c \cdot (a + b)$} & \bl{$\equiv^?$} & \bl{$(c \cdot a) + (c \cdot b)$} & \onslide<12->{\YES}\\ |
|
192 &\bl{$a^*$} & \bl{$\equiv^?$} & \bl{$\epsilon + (a \cdot a^*)$} & \onslide<13->{\YES} |
|
193 \end{tabular} |
|
194 \end{center} |
|
195 |
|
196 \end{frame}} |
|
197 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
198 |
|
199 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
200 \mode<presentation>{ |
|
201 \begin{frame}[c] |
266 \begin{frame}[c] |
202 \frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}} |
267 \frametitle{\begin{tabular}{c}The Specification\\[-1mm] for Matching\end{tabular}} |
203 |
268 |
204 \large |
269 \large |
205 a regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if |
270 A regular expression \bl{$r$} matches a string \bl{$s$}\\ if and only if |
206 |
271 |
207 \begin{center} |
272 \begin{center} |
208 \bl{$s \in L(r)$}\\ |
273 \bl{$s \in L(r)$}\\ |
209 \end{center}\bigskip\bigskip\pause |
274 \end{center} |
210 |
275 |
211 \end{frame}} |
276 \end{frame} |
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
277 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
213 |
278 |
214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
215 \mode<presentation>{ |
280 \mode<presentation>{ |
216 \begin{frame}[t] |
281 \begin{frame}[c] |
217 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
282 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
218 |
283 |
219 \mbox{}\\[-13mm] |
284 \begin{center} |
220 |
285 \begin{tikzpicture} |
221 \begin{tikzpicture}[y=.2cm, x=.3cm] |
286 \begin{axis}[ |
222 %axis |
287 xlabel={\pcode{a}s}, |
223 \draw (0,0) -- coordinate (x axis mid) (30,0); |
288 ylabel={time in secs}, |
224 \draw (0,0) -- coordinate (y axis mid) (0,30); |
289 enlargelimits=false, |
225 %ticks |
290 xtick={0,5,...,30}, |
226 \foreach \x in {0,5,...,30} |
291 xmax=30, |
227 \draw (\x,1pt) -- (\x,-3pt) |
292 ymax=35, |
228 node[anchor=north] {\x}; |
293 ytick={0,5,...,30}, |
229 \foreach \y in {0,5,...,30} |
294 scaled ticks=false, |
230 \draw (1pt,\y) -- (-3pt,\y) |
295 axis lines=left, |
231 node[anchor=east] {\y}; |
296 width=9cm, |
232 %labels |
297 height=7cm, |
233 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
298 legend entries={Python,Ruby}, |
234 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
299 legend pos=north west, |
235 |
300 legend cell align=left |
236 %plots |
301 ] |
237 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
302 \addplot[blue,mark=*, mark options={fill=white}] |
238 file {re-python.data}; |
303 table {re-python.data}; |
239 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
304 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
240 file {re-ruby.data}; |
305 table {re-ruby.data}; |
241 |
306 \end{axis} |
242 %legend |
|
243 \begin{scope}[shift={(4,20)}] |
|
244 \draw[color=blue] (0,0) -- |
|
245 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
246 node[right]{\small Python}; |
|
247 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
248 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
249 node[right]{\small Ruby}; |
|
250 \end{scope} |
|
251 \end{tikzpicture} |
307 \end{tikzpicture} |
|
308 \end{center} |
252 |
309 |
253 \end{frame}} |
310 \end{frame}} |
254 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
311 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
255 |
312 |
256 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
313 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
332 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
378 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\epsilon$ else $\varnothing$} & \\ |
333 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
379 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
334 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
380 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
335 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
381 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
336 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
382 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
337 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\smallskip\\\pause |
383 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\\pause |
338 |
384 |
339 \bl{$der\!s\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
385 \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
340 \bl{$der\!s\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$der\!s\,s\,(der\,c\,r)$} & \\ |
386 \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ |
341 \end{tabular} |
387 \end{tabular} |
342 \end{center} |
388 \end{center} |
343 |
389 |
344 \only<3->{ |
390 \end{frame}} |
345 \begin{textblock}{10.5}(2,5) |
391 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
392 |
|
393 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
394 \mode<presentation>{ |
|
395 \begin{frame}[c] |
|
396 \frametitle{\begin{tabular}{c}Examples\end{tabular}} |
|
397 |
|
398 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
|
399 |
|
400 \begin{center} |
|
401 \begin{tabular}{l} |
|
402 \bl{$der\,a\,r =?$}\\ |
|
403 \bl{$der\,b\,r =?$}\\ |
|
404 \bl{$der\,c\,r =?$} |
|
405 \end{tabular} |
|
406 \end{center} |
|
407 |
|
408 |
|
409 \end{frame}} |
|
410 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
411 |
|
412 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
413 \mode<presentation>{ |
|
414 \begin{frame}[t] |
|
415 \frametitle{The Algorithm} |
|
416 |
|
417 \begin{center} |
|
418 \begin{tabular}{@{}rll@{}} |
|
419 Input: & \bl{$r_1$}, \bl{$abc$}\medskip\\ |
|
420 Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = der\,a\,r_1)$}\smallskip\\ |
|
421 Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = der\,b\,r_2)$}\smallskip\\ |
|
422 Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = der\,b\,r_3)$}\smallskip\\ |
|
423 Step 4: & the string is exhausted; test & (\bl{$nullable(r_4)$})\\ |
|
424 & whether \bl{$r_4$} can recognise\\ |
|
425 & the empty string\smallskip\\ |
|
426 Output: & result of the test\\ |
|
427 & $\Rightarrow true \,\text{or}\, \textit{false}$\\ |
|
428 \end{tabular} |
|
429 \end{center} |
|
430 |
|
431 |
|
432 \end{frame}} |
|
433 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
434 |
|
435 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
436 \mode<presentation>{ |
|
437 \begin{frame}[c] |
|
438 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
439 |
|
440 \begin{center} |
346 \begin{tikzpicture} |
441 \begin{tikzpicture} |
347 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] |
442 \begin{axis}[ |
348 {\normalsize\color{darkgray} |
443 xlabel={\pcode{a}s}, |
349 \begin{minipage}{10.5cm} |
444 ylabel={time in secs}, |
350 \hspace{5mm}\mbox{{\lstset{language=Scala}\fontsize{8}{10}\selectfont |
445 enlargelimits=false, |
351 \texttt{\lstinputlisting{../progs/app6.scala}}}} |
446 xtick={0,5,...,30}, |
352 \end{minipage}}; |
447 xmax=30, |
|
448 ytick={0,5,...,30}, |
|
449 scaled ticks=false, |
|
450 axis lines=left, |
|
451 width=7cm, |
|
452 height=7cm, |
|
453 legend entries={Python,Ruby,Scala V1}, |
|
454 legend pos=outer north east, |
|
455 legend cell align=left |
|
456 ] |
|
457 \addplot[blue,mark=*, mark options={fill=white}] |
|
458 table {re-python.data}; |
|
459 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
|
460 table {re-ruby.data}; |
|
461 \addplot[red,mark=triangle*,mark options={fill=white}] |
|
462 table {re1.data}; |
|
463 \end{axis} |
353 \end{tikzpicture} |
464 \end{tikzpicture} |
354 \end{textblock}} |
465 \end{center} |
355 |
466 |
356 \end{frame}} |
467 \end{frame}} |
357 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
469 |
|
470 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
471 \mode<presentation>{ |
|
472 \begin{frame}[c] |
|
473 \frametitle{\begin{tabular}{c}A Problem\end{tabular}} |
|
474 |
|
475 We represented the ``n-times'' \bl{$a\{n\}$} as a sequence regular expression: |
|
476 |
|
477 \begin{center} |
|
478 \begin{tabular}{rl} |
|
479 1: & \bl{$a$}\\ |
|
480 2: & \bl{$a\cdot a$}\\ |
|
481 3: & \bl{$a\cdot a\cdot a$}\\ |
|
482 & \ldots\\ |
|
483 13: & \bl{$a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a$}\\ |
|
484 & \ldots\\ |
|
485 20: |
|
486 \end{tabular} |
|
487 \end{center} |
|
488 |
|
489 This problem is aggravated with \bl{$a?$} being represented as \bl{$\epsilon + a$}. |
|
490 \end{frame}} |
|
491 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
492 |
|
493 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
494 \mode<presentation>{ |
|
495 \begin{frame}[c] |
|
496 \frametitle{\begin{tabular}{c}Solving the Problem\end{tabular}} |
|
497 |
|
498 What happens if we extend our regular expressions |
|
499 |
|
500 \begin{center} |
|
501 \begin{tabular}{rcl} |
|
502 \bl{$r$} & \bl{$::=$} & \bl{\ldots}\\ |
|
503 & \bl{$\mid$} & \bl{$r\{n\}$}\\ |
|
504 & \bl{$\mid$} & \bl{$r?$} |
|
505 \end{tabular} |
|
506 \end{center} |
|
507 |
|
508 What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}? |
|
509 \end{frame}} |
|
510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
511 |
|
512 |
|
513 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
514 \mode<presentation>{ |
|
515 \begin{frame}[t] |
|
516 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
517 |
|
518 \begin{center} |
|
519 \begin{tikzpicture} |
|
520 \begin{axis}[ |
|
521 xlabel={\pcode{a}s}, |
|
522 ylabel={time in secs}, |
|
523 enlargelimits=false, |
|
524 xtick={0,200,...,1000}, |
|
525 xmax=1000, |
|
526 ytick={0,5,...,30}, |
|
527 scaled ticks=false, |
|
528 axis lines=left, |
|
529 width=9.5cm, |
|
530 height=7cm, |
|
531 legend entries={Python,Ruby,Scala V1,Scala V2}, |
|
532 legend pos=north west, |
|
533 legend cell align=left |
|
534 ] |
|
535 \addplot[blue,mark=*, mark options={fill=white}] |
|
536 table {re-python.data}; |
|
537 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
|
538 table {re-ruby.data}; |
|
539 \addplot[red,mark=triangle*,mark options={fill=white}] |
|
540 table {re1.data}; |
|
541 \addplot[green,mark=square*,mark options={fill=white}] |
|
542 table {re2b.data}; |
|
543 \end{axis} |
|
544 \end{tikzpicture} |
|
545 \end{center} |
|
546 |
|
547 \end{frame}} |
|
548 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
549 |
358 |
550 |
359 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
551 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
360 \mode<presentation>{ |
552 \mode<presentation>{ |
361 \begin{frame}[c] |
553 \begin{frame}[c] |
362 \frametitle{\begin{tabular}{c}Examples\end{tabular}} |
554 \frametitle{\begin{tabular}{c}Examples\end{tabular}} |
363 |
555 |
364 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
556 Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with |
365 |
557 |
366 \begin{center} |
558 \begin{center} |
367 \begin{tabular}{l} |
559 \begin{tabular}{l} |
368 \bl{$der\,a\,r$}\\ |
560 \bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\ |
369 \bl{$der\,b\,r$} |
561 \bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$}\\ |
|
562 \bl{$der\,c\,r = ((\varnothing \cdot b) + \varnothing)\cdot r$} |
370 \end{tabular} |
563 \end{tabular} |
371 \end{center} |
564 \end{center} |
372 |
565 |
373 |
566 What are these regular expressions equivalent to? |
374 \end{frame}} |
567 |
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
568 \end{frame}} |
|
569 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
570 |
|
571 |
376 |
572 |
377 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
573 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
378 \mode<presentation>{ |
574 \mode<presentation>{ |
379 \begin{frame}[t] |
575 \begin{frame}[t] |
380 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
576 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
381 |
577 |
382 \mbox{}\\[-13mm] |
578 \begin{center} |
383 |
579 \begin{tikzpicture} |
384 \begin{tikzpicture}[y=.2cm, x=.3cm] |
580 \begin{axis}[ |
385 %axis |
581 xlabel={\pcode{a}s}, |
386 \draw (0,0) -- coordinate (x axis mid) (30,0); |
582 ylabel={time in secs}, |
387 \draw (0,0) -- coordinate (y axis mid) (0,30); |
583 enlargelimits=false, |
388 %ticks |
584 xtick={0,3000,...,12000}, |
389 \foreach \x in {0,5,...,30} |
585 xmax=12000, |
390 \draw (\x,1pt) -- (\x,-3pt) |
586 ymax=35, |
391 node[anchor=north] {\x}; |
587 ytick={0,5,...,30}, |
392 \foreach \y in {0,5,...,30} |
588 scaled ticks=false, |
393 \draw (1pt,\y) -- (-3pt,\y) |
589 axis lines=left, |
394 node[anchor=east] {\y}; |
590 width=9cm, |
395 %labels |
591 height=7cm |
396 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
592 ] |
397 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
593 \addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; |
398 |
594 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
399 %plots |
595 \end{axis} |
400 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
401 file {re-python.data}; |
|
402 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
403 file {re1.data}; |
|
404 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
405 file {re-ruby.data}; |
|
406 |
|
407 |
|
408 %legend |
|
409 \begin{scope}[shift={(4,20)}] |
|
410 \draw[color=blue] (0,0) -- |
|
411 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
412 node[right]{\small Python}; |
|
413 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
414 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
415 node[right]{\small Ruby}; |
|
416 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
417 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
418 node[right]{\small Scala V1}; |
|
419 \end{scope} |
|
420 \end{tikzpicture} |
596 \end{tikzpicture} |
|
597 \end{center} |
421 |
598 |
422 \end{frame}} |
599 \end{frame}} |
423 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
600 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
424 |
601 |
425 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
602 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
521 \frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}} |
727 \frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}} |
522 |
728 |
523 We can finally prove |
729 We can finally prove |
524 |
730 |
525 \begin{center} |
731 \begin{center} |
526 \bl{$matcher(r, s)$} if and only if \bl{$s \in L(r)$} |
732 \bl{$matches(r, s)$} if and only if \bl{$s \in L(r)$} |
527 \end{center} |
733 \end{center} |
528 |
734 |
529 |
735 |
530 \end{frame}} |
736 \end{frame}} |
531 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
737 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
532 |
|
533 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
534 \mode<presentation>{ |
|
535 \begin{frame}[t] |
|
536 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
537 |
|
538 \mbox{}\\[-13mm] |
|
539 |
|
540 \begin{tikzpicture}[y=.2cm, x=.3cm] |
|
541 %axis |
|
542 \draw (0,0) -- coordinate (x axis mid) (30,0); |
|
543 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
544 %ticks |
|
545 \foreach \x in {0,5,...,30} |
|
546 \draw (\x,1pt) -- (\x,-3pt) |
|
547 node[anchor=north] {\x}; |
|
548 \foreach \y in {0,5,...,30} |
|
549 \draw (1pt,\y) -- (-3pt,\y) |
|
550 node[anchor=east] {\y}; |
|
551 %labels |
|
552 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
553 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
554 |
|
555 %plots |
|
556 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
557 file {re-python.data}; |
|
558 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
559 file {re1.data}; |
|
560 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
561 file {re-ruby.data}; |
|
562 |
|
563 |
|
564 %legend |
|
565 \begin{scope}[shift={(4,20)}] |
|
566 \draw[color=blue] (0,0) -- |
|
567 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
568 node[right]{\small Python}; |
|
569 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
570 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
571 node[right]{\small Ruby}; |
|
572 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
573 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
574 node[right]{\small Scala V1}; |
|
575 \end{scope} |
|
576 \end{tikzpicture} |
|
577 |
|
578 \end{frame}} |
|
579 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
580 |
|
581 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
582 \mode<presentation>{ |
|
583 \begin{frame}[c] |
|
584 \frametitle{\begin{tabular}{c}A Problem\end{tabular}} |
|
585 |
|
586 We represented the ``n-times'' \bl{$a\{n\}$} as a sequence regular expression: |
|
587 |
|
588 \begin{center} |
|
589 \begin{tabular}{rl} |
|
590 1: & \bl{$a$}\\ |
|
591 2: & \bl{$a\cdot a$}\\ |
|
592 3: & \bl{$a\cdot a\cdot a$}\\ |
|
593 & \ldots\\ |
|
594 13: & \bl{$a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a\cdot a$}\\ |
|
595 & \ldots\\ |
|
596 20: |
|
597 \end{tabular} |
|
598 \end{center} |
|
599 |
|
600 This problem is aggravated with \bl{$a?$} being represented as \bl{$\epsilon + a$}. |
|
601 \end{frame}} |
|
602 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
603 |
|
604 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
605 \mode<presentation>{ |
|
606 \begin{frame}[c] |
|
607 \frametitle{\begin{tabular}{c}Solving the Problem\end{tabular}} |
|
608 |
|
609 What happens if we extend our regular expressions |
|
610 |
|
611 \begin{center} |
|
612 \begin{tabular}{rcl} |
|
613 \bl{$r$} & \bl{$::=$} & \bl{\ldots}\\ |
|
614 & \bl{$\mid$} & \bl{$r\{n\}$}\\ |
|
615 & \bl{$\mid$} & \bl{$r?$} |
|
616 \end{tabular} |
|
617 \end{center} |
|
618 |
|
619 What is their meaning? What are the cases for \bl{$nullable$} and \bl{$der$}? |
|
620 \end{frame}} |
|
621 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
622 |
|
623 |
|
624 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
625 \mode<presentation>{ |
|
626 \begin{frame}[t] |
|
627 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
628 |
|
629 \mbox{}\\[-13mm] |
|
630 |
|
631 \begin{tikzpicture}[y=.2cm, x=.12cm] |
|
632 %axis |
|
633 \draw (0,0) -- coordinate (x axis mid) (70,0); |
|
634 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
635 %ticks |
|
636 \foreach \x in {0,10,...,70} |
|
637 \draw (\x,1pt) -- (\x,-3pt) |
|
638 node[anchor=north] {\x}; |
|
639 \foreach \y in {0,5,...,30} |
|
640 \draw (1pt,\y) -- (-3pt,\y) |
|
641 node[anchor=east] {\y}; |
|
642 %labels |
|
643 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
644 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
645 |
|
646 %plots |
|
647 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
648 file {re-python.data}; |
|
649 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
650 file {re1.data}; |
|
651 \draw[color=green] plot[mark=square*, mark options={fill=white} ] |
|
652 file {re2a.data}; |
|
653 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
654 file {re-ruby.data}; |
|
655 |
|
656 %legend |
|
657 \begin{scope}[shift={(4,20)}] |
|
658 \draw[color=blue] (0,0) -- |
|
659 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
660 node[right]{\small Python}; |
|
661 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
662 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
663 node[right]{\small Ruby}; |
|
664 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
665 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
666 node[right]{\small Scala V1}; |
|
667 \draw[yshift=2\baselineskip, color=green] (0,0) -- |
|
668 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
669 node[right]{\small Scala V2}; |
|
670 \end{scope} |
|
671 \end{tikzpicture} |
|
672 |
|
673 \end{frame}} |
|
674 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
675 |
|
676 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
677 \mode<presentation>{ |
|
678 \begin{frame}[t] |
|
679 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
680 |
|
681 \mbox{}\\[-13mm] |
|
682 |
|
683 \begin{tabular}{@ {\hspace{-5mm}}l} |
|
684 \begin{tikzpicture}[y=.2cm, x=.01cm] |
|
685 %axis |
|
686 \draw (0,0) -- coordinate (x axis mid) (1000,0); |
|
687 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
688 %ticks |
|
689 \foreach \x in {0,100,...,1000} |
|
690 \draw (\x,1pt) -- (\x,-3pt) |
|
691 node[anchor=north] {\x}; |
|
692 \foreach \y in {0,5,...,30} |
|
693 \draw (1pt,\y) -- (-3pt,\y) |
|
694 node[anchor=east] {\y}; |
|
695 %labels |
|
696 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
697 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
698 |
|
699 %plots |
|
700 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
701 file {re-python.data}; |
|
702 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
703 file {re1.data}; |
|
704 \draw[color=green] plot[mark=square*, mark options={fill=white} ] |
|
705 file {re2b.data}; |
|
706 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
707 file {re-ruby.data}; |
|
708 |
|
709 %legend |
|
710 \begin{scope}[shift={(100,20)}] |
|
711 \draw[color=blue] (0,0) -- |
|
712 plot[mark=*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
713 node[right]{\small Python}; |
|
714 \draw[yshift=-13, color=brown] (0,0) -- |
|
715 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
716 node[right]{\small Ruby}; |
|
717 \draw[yshift=13, color=red] (0,0) -- |
|
718 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
719 node[right]{\small Scala V1}; |
|
720 \draw[yshift=26, color=green] (0,0) -- |
|
721 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
722 node[right]{\small Scala V2}; |
|
723 \end{scope} |
|
724 \end{tikzpicture} |
|
725 \end{tabular} |
|
726 |
|
727 \end{frame}} |
|
728 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
729 |
|
730 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
731 \mode<presentation>{ |
|
732 \begin{frame}[c] |
|
733 \frametitle{\begin{tabular}{c}Examples\end{tabular}} |
|
734 |
|
735 Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with |
|
736 |
|
737 \begin{center} |
|
738 \begin{tabular}{l} |
|
739 \bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\ |
|
740 \bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$} |
|
741 \end{tabular} |
|
742 \end{center} |
|
743 |
|
744 What are these regular expressions equal to? |
|
745 |
|
746 \end{frame}} |
|
747 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
748 |
|
749 |
|
750 |
|
751 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
752 \mode<presentation>{ |
|
753 \begin{frame}[t] |
|
754 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
755 |
|
756 \mbox{}\\[-9mm] |
|
757 |
|
758 \begin{tabular}{@ {\hspace{-5mm}}l} |
|
759 \begin{tikzpicture}[y=.2cm, x=.0008cm] |
|
760 %axis |
|
761 \draw (0,0) -- coordinate (x axis mid) (12000,0); |
|
762 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
763 %ticks |
|
764 \foreach \x in {0,2000,...,12000} |
|
765 \draw (\x,1pt) -- (\x,-3pt) |
|
766 node[anchor=north] {\x}; |
|
767 \foreach \y in {0,5,...,30} |
|
768 \draw (1pt,\y) -- (-3pt,\y) |
|
769 node[anchor=east] {\y}; |
|
770 %labels |
|
771 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
772 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
773 |
|
774 %plots |
|
775 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
776 file {re1.data}; |
|
777 \draw[color=green] plot[mark=square*, mark options={fill=white} ] |
|
778 file {re2b.data}; |
|
779 \draw[color=black] plot[mark=square*, mark options={fill=white} ] |
|
780 file {re3.data}; |
|
781 |
|
782 %legend |
|
783 \begin{scope}[shift={(2000,20)}] |
|
784 \draw[color=red] (0,0) -- |
|
785 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
786 node[right]{\small Scala V1}; |
|
787 \draw[yshift=13, color=green] (0,0) -- |
|
788 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
789 node[right]{\small Scala V2}; |
|
790 \draw[yshift=26, color=black] (0,0) -- |
|
791 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
792 node[right]{\small Scala V3}; |
|
793 \end{scope} |
|
794 \end{tikzpicture} |
|
795 \end{tabular} |
|
796 |
|
797 \end{frame}} |
|
798 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
799 |
|
800 |
738 |
801 \end{document} |
739 \end{document} |
802 |
740 |
803 %%% Local Variables: |
741 %%% Local Variables: |
804 %%% mode: latex |
742 %%% mode: latex |