98 \end{tikzpicture} |
100 \end{tikzpicture} |
99 \end{tabular} |
101 \end{tabular} |
100 \end{center} |
102 \end{center} |
101 |
103 |
102 \small |
104 \small |
103 In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8. |
105 In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8, |
|
106 JavaScript and Python. |
104 |
107 |
105 \end{frame} |
108 \end{frame} |
106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
107 |
110 |
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
111 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 \begin{frame}[c] |
112 %\begin{frame}[c] |
110 \frametitle{Evil Regular Expressions} |
113 %\frametitle{Evil Regular Expressions} |
|
114 % |
|
115 %\begin{itemize} |
|
116 %\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
|
117 %\item Evil regular expressions\medskip |
|
118 %\begin{itemize} |
|
119 %\item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} |
|
120 %\item \bl{$(a^*)^*$} |
|
121 %\item \bl{$([a$\,-\,$z]^+)^*$} |
|
122 %\item \bl{$(a + a \cdot a)^*$} |
|
123 %\item \bl{$(a + a^?)^*$} |
|
124 %\end{itemize} |
|
125 % |
|
126 %\item sometimes also called \alert{catastrophic backtracking}\bigskip |
|
127 %\item \small\ldots I hope you have watched the video by the |
|
128 % StackExchange engineer |
|
129 %\end{itemize} |
|
130 % |
|
131 %\end{frame} |
|
132 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
133 |
|
134 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
135 \begin{frame}[c] |
|
136 \frametitle{(Basic) Regular Expressions} |
|
137 |
|
138 Their inductive definition: |
|
139 |
|
140 \begin{center} |
|
141 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
|
142 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ |
|
143 & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ |
|
144 & \bl{$\mid$} & \bl{$c$} & character\\ |
|
145 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
|
146 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
|
147 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
|
148 \end{tabular} |
|
149 \end{center} |
|
150 \vspace{\fill} |
|
151 |
|
152 Q: \;What about \;\bl{$r \cdot 0$} \; ? |
|
153 \end{frame} |
|
154 |
|
155 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
156 \begin{frame}[c] |
|
157 \frametitle{Languages (Sets of Strings)} |
111 |
158 |
112 \begin{itemize} |
159 \begin{itemize} |
113 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
|
114 \item Evil regular expressions\medskip |
|
115 \begin{itemize} |
|
116 \item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$} |
|
117 \item \bl{$(a^*)^*$} |
|
118 \item \bl{$([a$\,-\,$z]^+)^*$} |
|
119 \item \bl{$(a + a \cdot a)^*$} |
|
120 \item \bl{$(a + a^?)^*$} |
|
121 \end{itemize} |
|
122 |
|
123 \item sometimes also called \alert{catastrophic backtracking}\bigskip |
|
124 \item \small\ldots I hope you have watched the video by the |
|
125 StackExchange engineer |
|
126 \end{itemize} |
|
127 |
|
128 \end{frame} |
|
129 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
130 |
|
131 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
132 \begin{frame}[c] |
|
133 \frametitle{Languages} |
|
134 |
|
135 \begin{itemize} |
|
136 |
160 |
137 \item A \alert{\bf Language} is a set of strings, for example\medskip |
161 \item A \alert{\bf Language} is a set of strings, for example\medskip |
138 \begin{center} |
162 \begin{center} |
139 \bl{$\{[], hello, \textit{foobar}, a, abc\}$} |
163 \bl{$\{[], hello, foobar, a, abc\}$} |
140 \end{center}\bigskip |
164 \end{center}\bigskip |
141 |
165 |
142 \item \alert{\bf Concatenation} of strings and languages |
166 \item \alert{\bf Concatenation} for strings and languages |
143 |
167 |
144 \begin{center} |
168 \begin{center} |
145 \begin{tabular}{rcl} |
169 \begin{tabular}{rcl} |
146 \bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\ |
170 \bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\ |
147 \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} |
171 \bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$} |
148 \end{tabular} |
172 \end{tabular} |
149 \end{center} |
173 \end{center} |
150 \bigskip |
174 \bigskip |
151 |
175 |
152 \small |
176 \small |
155 \[ |
179 \[ |
156 \bl{A \,@\, B = \{fooa, foob, bara, barb\}} |
180 \bl{A \,@\, B = \{fooa, foob, bara, barb\}} |
157 \] |
181 \] |
158 |
182 |
159 \end{itemize} |
183 \end{itemize} |
160 |
184 \end{frame} |
161 \end{frame} |
185 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
162 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
186 |
|
187 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
188 \begin{frame}[c] |
|
189 \frametitle{Two Corner Cases} |
|
190 |
|
191 \Large |
|
192 \begin{center} |
|
193 \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\ |
|
194 \bl{$A \,@\, \{\} = \;?$} |
|
195 \end{center} |
|
196 |
|
197 \end{frame} |
|
198 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
199 |
|
200 |
|
201 |
|
202 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
203 \begin{frame}[c] |
|
204 \frametitle{ |
|
205 The Meaning of a\\[-2mm] |
|
206 Regular Expression} |
|
207 |
|
208 ...all the strings a regular expression can match. |
|
209 |
|
210 \begin{center} |
|
211 \begin{tabular}{rcl} |
|
212 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
|
213 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
|
214 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
|
215 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
|
216 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
|
217 \bl{$L(r^*)$} & \bl{$\dn$} & \\ |
|
218 \end{tabular} |
|
219 \end{center} |
|
220 |
|
221 \begin{textblock}{14}(1.5,13.5)\small |
|
222 \bl{$L$} is a function from regular expressions to |
|
223 sets of strings (languages):\smallskip\\ |
|
224 \bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
|
225 \end{textblock} |
|
226 |
|
227 \end{frame} |
|
228 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
229 |
|
230 |
163 |
231 |
164 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
165 \begin{frame}[c] |
233 \begin{frame}[c] |
166 \frametitle{The Power Operation} |
234 \frametitle{The Power Operation} |
167 |
235 |
190 \end{frame} |
258 \end{frame} |
191 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
259 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
192 |
260 |
193 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
194 \begin{frame}[c] |
262 \begin{frame}[c] |
195 \frametitle{Homework Question} |
263 \frametitle{Homework Question} |
196 |
264 |
197 \begin{itemize} |
265 \begin{itemize} |
198 \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip |
266 \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip |
199 |
267 |
200 \begin{center} |
268 \item[] |
201 How many strings are in \bl{$A^4$}? |
269 How many strings are in \bl{$A^4$}\,? |
202 \end{center}\bigskip\medskip\pause |
270 \bigskip\medskip\pause |
203 |
271 |
204 |
272 |
205 \begin{center} |
273 \item[] |
206 \begin{tabular}{l} |
274 What if \bl{$A = \{[a],[b],[c],[]\}$};\\ |
207 What if \bl{$A = \{[a],[b],[c],[]\}$};\\ |
275 how many strings are then in \bl{$A^4$}\,? |
208 how many strings are then in \bl{$A^4$}? |
276 \end{itemize} |
209 \end{tabular} |
277 |
210 \end{center} |
278 \end{frame} |
211 \end{itemize} |
279 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
212 |
|
213 \end{frame} |
|
214 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
215 |
280 |
216 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
281 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
217 \begin{frame}[c] |
282 \begin{frame}[c] |
218 \frametitle{The Star Operation} |
283 \frametitle{The Star Operation} |
219 |
284 |
250 \begin{frame}[c] |
315 \begin{frame}[c] |
251 \frametitle{ |
316 \frametitle{ |
252 The Meaning of a\\[-2mm] |
317 The Meaning of a\\[-2mm] |
253 Regular Expression} |
318 Regular Expression} |
254 |
319 |
255 \begin{textblock}{15}(1,4) |
320 ...all the strings a regular expression can match. |
|
321 |
|
322 \begin{center} |
256 \begin{tabular}{rcl} |
323 \begin{tabular}{rcl} |
257 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
324 \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ |
258 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
325 \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ |
259 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
326 \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ |
260 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
327 \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ |
261 \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) \}$}\\ |
328 \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ |
262 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ |
329 \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ |
263 \end{tabular} |
330 \end{tabular} |
264 \end{textblock} |
331 \end{center} |
265 |
332 |
266 \begin{textblock}{9}(6,12)\small |
333 %\begin{textblock}{9}(6,12)\small |
267 \bl{$L$} is a function from regular expressions to |
334 %\bl{$L$} is a function from regular expressions to |
268 sets of strings (languages):\smallskip\\ |
335 %sets of strings (languages):\smallskip\\ |
269 \bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
336 %\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} |
270 \end{textblock} |
337 %\end{textblock} |
271 |
338 |
272 \end{frame} |
339 \end{frame} |
273 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
340 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
274 |
341 |
275 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
342 |
276 \begin{frame}[c] |
343 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
277 \frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}} |
344 \begin{frame}[c] |
278 |
345 \frametitle{ |
279 \bigskip |
346 When Are Two Regular\\[-1mm] |
280 homework (written exam 80\%)\\ |
347 Expressions Equivalent?} |
281 coursework (20\%; first one today)\\ |
348 |
282 submission Fridays @ 18:00 -- accepted until Mondays |
349 \begin{bubble}[10cm] |
283 \mbox{} |
350 \large |
284 \end{frame} |
351 Two regular expressions \bl{$r_1$} and \bl{$r_2$} are equivalent |
285 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
352 provided:\medskip |
286 |
353 \begin{center} |
287 |
354 \bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$} |
288 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
355 \end{center}\medskip |
289 \begin{frame}[t] |
356 \end{bubble} |
290 \frametitle{Semantic Derivative\\[5mm]} |
357 |
291 |
358 \end{frame} |
292 |
359 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
293 |
360 |
294 \begin{itemize} |
361 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
295 \item The \alert{\bf Semantic Derivative} of a |
362 \begin{frame}[c] |
296 \underline{language}\\ w.r.t.~to a character \bl{$c$}: |
363 \frametitle{Some Concrete Equivalences} |
297 \bigskip |
|
298 |
|
299 \begin{center} |
|
300 \bl{$\Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
|
301 \end{center}\bigskip |
|
302 |
|
303 For \bl{$A = \{\mathit{foo}, \mathit{bar}, \mathit{frak}\}$} then |
|
304 |
|
305 \begin{center} |
|
306 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
|
307 $\Der\,f\,A$ & $=$ & $\{\mathit{oo}, \mathit{rak}\}$\\ |
|
308 $\Der\,b\,A$ & $=$ & $\{\mathit{ar}\}$\\ |
|
309 $\Der\,a\,A$ & $=$ & $\{\}$\pause |
|
310 \end{tabular}} |
|
311 \end{center} |
|
312 |
|
313 |
|
314 We can extend this definition to strings |
|
315 \[ |
|
316 \bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}} |
|
317 \] |
|
318 |
|
319 \end{itemize} |
|
320 |
|
321 \end{frame} |
|
322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
323 |
|
324 |
|
325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
326 \begin{frame}[c] |
|
327 \frametitle{The Specification for Matching} |
|
328 |
|
329 \begin{bubble}[10cm] |
|
330 \large |
|
331 A regular expression \bl{$r$} matches a string~\bl{$s$} |
|
332 provided |
|
333 \begin{center} |
|
334 \bl{$s \in L(r)$} |
|
335 \end{center} |
|
336 \end{bubble} |
|
337 |
|
338 \bigskip\bigskip |
|
339 |
|
340 \ldots and the point of the this lecture is to decide this problem as |
|
341 fast as possible (unlike Python, Ruby, Java etc) |
|
342 |
|
343 \end{frame} |
|
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
345 |
|
346 |
|
347 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
348 \begin{frame}[t] |
|
349 \frametitle{Regular Expressions} |
|
350 |
|
351 Their inductive definition: |
|
352 |
|
353 |
|
354 \begin{textblock}{6}(2,7.5) |
|
355 \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l} |
|
356 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$} & nothing\\ |
|
357 & \bl{$\mid$} & \bl{$\ONE$} & empty string / \pcode{""} / $[]$\\ |
|
358 & \bl{$\mid$} & \bl{$c$} & single character\\ |
|
359 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\ |
|
360 & \bl{$\mid$} & \bl{$r_1 + r_2$} & alternative / choice\\ |
|
361 & \bl{$\mid$} & \bl{$r^*$} & star (zero or more)\\ |
|
362 \end{tabular} |
|
363 \end{textblock} |
|
364 |
|
365 \only<2->{\footnotesize |
|
366 \begin{textblock}{9}(2,0.5) |
|
367 \begin{bubble}[9.8cm] |
|
368 \lstinputlisting{../progs/app01.scala} |
|
369 \end{bubble} |
|
370 \end{textblock}} |
|
371 |
|
372 \end{frame} |
|
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
374 |
|
375 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
376 \begin{frame}[c] |
|
377 \frametitle{ |
|
378 When Are Two Regular\\[-1mm] |
|
379 Expressions Equivalent?} |
|
380 |
|
381 \large |
|
382 \begin{center} |
|
383 \bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$} |
|
384 \end{center} |
|
385 |
|
386 \end{frame} |
|
387 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
388 |
|
389 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
390 \begin{frame}[t] |
|
391 \frametitle{Concrete Equivalences} |
|
392 |
364 |
393 \begin{center} |
365 \begin{center} |
394 \bl{\begin{tabular}{rcl} |
366 \bl{\begin{tabular}{rcl} |
395 $(a + b) + c$ & $\equiv$ & $a + (b + c)$\\ |
367 $(a + b) + c$ & $\equiv$ & $a + (b + c)$\\ |
396 $a + a$ & $\equiv$ & $a$\\ |
368 $a + a$ & $\equiv$ & $a$\\ |
435 $r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\ |
407 $r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\ |
436 $\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\ |
408 $\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\ |
437 $r + r$ & $\equiv$ & $r$ |
409 $r + r$ & $\equiv$ & $r$ |
438 \end{tabular}} |
410 \end{tabular}} |
439 \end{center} |
411 \end{center} |
440 |
412 |
441 \end{frame} |
413 \end{frame} |
442 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
414 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
443 |
415 |
444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
416 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
445 \begin{frame}[c] |
417 \begin{frame}[c] |
446 \frametitle{Another Homework Question} |
418 \frametitle{The Specification for Matching} |
|
419 |
|
420 \begin{bubble}[10cm] |
|
421 \large |
|
422 A regular expression \bl{$r$} matches a string~\bl{$s$} |
|
423 provided: |
|
424 \begin{center} |
|
425 \bl{$s \in L(r)$} |
|
426 \end{center}\medskip |
|
427 \end{bubble} |
|
428 |
|
429 \bigskip\bigskip |
|
430 |
|
431 \ldots and the point of the this lecture is to decide this problem as |
|
432 fast as possible (unlike Python, Ruby, Java etc) |
|
433 |
|
434 \end{frame} |
|
435 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
436 |
|
437 |
|
438 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
439 \begin{frame}[c] |
|
440 \frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}} |
|
441 |
|
442 \bigskip |
|
443 homework (written exam 80\%)\\ |
|
444 coursework (20\%; first one today)\\ |
|
445 submission Fridays @ 18:00 -- accepted until Mondays |
|
446 \mbox{} |
|
447 \end{frame} |
|
448 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
449 |
|
450 |
|
451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
452 \begin{frame}[t] |
|
453 \frametitle{Semantic Derivative\\[5mm]} |
447 |
454 |
448 \begin{itemize} |
455 \begin{itemize} |
449 \item How many basic regular expressions are there to match |
456 \item The \alert{\bf Semantic Derivative} of a |
450 the string \bl{$abcd$}\,?\pause |
457 \underline{language}\\ w.r.t.~to a character \bl{$c$}: |
451 \item How many if they cannot include |
458 \bigskip |
452 \bl{$\ONE$} and \bl{$\ZERO$}\/?\pause |
459 |
453 \item How many if they are also not |
460 \begin{center} |
454 allowed to contain stars?\pause |
461 \bl{$\Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
455 \item How many if they are also |
462 \end{center}\bigskip |
456 not allowed to contain \bl{$\_ + \_$}\/? |
463 |
457 \end{itemize} |
464 For \bl{$A = \{\mathit{foo}, \mathit{bar}, \mathit{frak}\}$} then |
458 |
465 |
459 \end{frame} |
466 \begin{center} |
460 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
467 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
|
468 $\Der\,f\,A$ & $=$ & $\{\mathit{oo}, \mathit{rak}\}$\\ |
|
469 $\Der\,b\,A$ & $=$ & $\{\mathit{ar}\}$\\ |
|
470 $\Der\,a\,A$ & $=$ & $\{\}$\pause |
|
471 \end{tabular}} |
|
472 \end{center}\medskip |
|
473 |
|
474 |
|
475 We can extend this definition to strings |
|
476 \[ |
|
477 \bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}} |
|
478 \] |
|
479 |
|
480 \end{itemize} |
|
481 |
|
482 \end{frame} |
|
483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
484 |
461 |
485 |
462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
486 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
463 \begin{frame}[c] |
487 \begin{frame}[c] |
464 \frametitle{\mbox{Brzozowski's Algorithm (1)}} |
488 \frametitle{\mbox{Brzozowski's Algorithm (1)}} |
465 |
489 |
504 \bl{$\der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\ |
528 \bl{$\der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\ |
505 \bl{$\der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$\der\, c\, r_1 + \der\, c\, r_2$} & \\ |
529 \bl{$\der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$\der\, c\, r_1 + \der\, c\, r_2$} & \\ |
506 \bl{$\der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
530 \bl{$\der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
507 & & \bl{then $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}\\ |
531 & & \bl{then $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}\\ |
508 & & \bl{else $(\der\, c\, r_1) \cdot r_2$}\\ |
532 & & \bl{else $(\der\, c\, r_1) \cdot r_2$}\\ |
509 \bl{$\der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\bigskip\\\pause |
533 \bl{$\der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\medskip\bigskip\\\pause |
510 |
534 |
511 \bl{$\ders\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
535 \bl{$\ders\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
512 \bl{$\ders\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\ders\,s\,(\der\,c\,r)$} & \\ |
536 \bl{$\ders\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\ders\,s\,(\der\,c\,r)$} & \\ |
513 \end{tabular} |
537 \end{tabular} |
514 \end{center} |
538 \end{center} |
1029 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1055 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1030 |
1056 |
1031 |
1057 |
1032 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1058 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1033 \begin{frame}[c] |
1059 \begin{frame}[c] |
1034 \frametitle{\begin{tabular}{c} |
1060 \frametitle{Correctness Proof \\[-1mm] |
1035 Correctness Proof\\[-1mm] for our Matcher\end{tabular}} |
1061 for our Matcher} |
1036 |
1062 |
1037 \begin{itemize} |
1063 \begin{itemize} |
1038 \item We started from |
1064 \item We started from |
1039 |
1065 |
1040 \begin{center} |
1066 \begin{center} |
1041 \begin{tabular}{rp{4cm}} |
1067 \begin{tabular}{rp{4cm}} |
1042 & \bl{$s \in L(r)$}\medskip\\ |
1068 & \bl{$s \in L(r)$}\medskip\\ |
1043 \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause |
1069 \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause |
1044 \end{tabular} |
1070 \end{tabular} |
1045 \end{center} |
1071 \end{center}\bigskip |
1046 |
1072 |
1047 \item if we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we |
1073 \item if we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we |
1048 have |
1074 have\bigskip |
1049 |
1075 |
1050 \begin{center} |
1076 \begin{center} |
1051 \begin{tabular}{rp{4cm}} |
1077 \begin{tabular}{rp{4cm}} |
1052 \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\ |
1078 \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\ |
1053 \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\ |
1079 \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\ |