33 |
33 |
34 \normalsize |
34 \normalsize |
35 \begin{center} |
35 \begin{center} |
36 \begin{tabular}{ll} |
36 \begin{tabular}{ll} |
37 Email: & christian.urban at kcl.ac.uk\\ |
37 Email: & christian.urban at kcl.ac.uk\\ |
38 Office: & N\liningnums{7.07} (North Wing, Bush House)\\ |
38 Office: & N7.07 (North Wing, Bush House)\\ |
39 Slides: & KEATS (also homework is there) |
39 Slides: & KEATS (also homework is there) |
40 \end{tabular} |
40 \end{tabular} |
41 \end{center} |
41 \end{center} |
42 |
42 |
43 \end{frame} |
43 \end{frame} |
44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
44 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
45 |
45 |
46 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
46 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
47 \begin{frame}[t] |
47 \begin{frame}[t] |
48 \frametitle{\Large |
48 \frametitle{ |
49 Lets Implement an Efficient\\[-2mm] |
49 Lets Implement an Efficient\\[-2mm] |
50 Regular Expression Matcher} |
50 Regular Expression Matcher} |
51 |
51 |
52 \footnotesize |
52 \footnotesize |
53 \begin{center} |
53 \begin{center} |
298 |
298 |
299 \begin{center} |
299 \begin{center} |
300 \bl{$\Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
300 \bl{$\Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
301 \end{center}\bigskip |
301 \end{center}\bigskip |
302 |
302 |
303 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then |
303 For \bl{$A = \{\mathit{foo}, \mathit{bar}, \mathit{frak}\}$} then |
304 |
304 |
305 \begin{center} |
305 \begin{center} |
306 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
306 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
307 $\Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\ |
307 $\Der\,f\,A$ & $=$ & $\{\mathit{oo}, \mathit{rak}\}$\\ |
308 $\Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\ |
308 $\Der\,b\,A$ & $=$ & $\{\mathit{ar}\}$\\ |
309 $\Der\,a\,A$ & $=$ & $\{\}$\pause |
309 $\Der\,a\,A$ & $=$ & $\{\}$\pause |
310 \end{tabular}} |
310 \end{tabular}} |
311 \end{center} |
311 \end{center} |
312 |
312 |
313 \small |
313 |
314 We can extend this definition to strings |
314 We can extend this definition to strings |
315 \[ |
315 \[ |
316 \bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}} |
316 \bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}} |
317 \] |
317 \] |
318 |
318 |
322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
322 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
323 |
323 |
324 |
324 |
325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
325 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
326 \begin{frame}[c] |
326 \begin{frame}[c] |
327 \frametitle{The Specification\\ for Matching} |
327 \frametitle{The Specification for Matching} |
328 |
328 |
329 \begin{bubble}[10cm] |
329 \begin{bubble}[10cm] |
330 \large |
330 \large |
331 A regular expression \bl{$r$} matches a string~\bl{$s$} |
331 A regular expression \bl{$r$} matches a string~\bl{$s$} |
332 provided |
332 provided |
333 |
333 \begin{center} |
334 \begin{center} |
334 \bl{$s \in L(r)$} |
335 \bl{$s \in L(r)$}\\ |
335 \end{center} |
336 \end{center} |
336 \end{bubble} |
337 \end{bubble}\bigskip\bigskip |
337 |
338 |
338 \bigskip\bigskip |
339 \ldots and the point of the this lecture is |
339 |
340 to decide this problem as fast as possible |
340 \ldots and the point of the this lecture is to decide this problem as |
341 (unlike Python, Ruby, Java etc) |
341 fast as possible (unlike Python, Ruby, Java etc) |
342 |
342 |
343 \end{frame} |
343 \end{frame} |
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
344 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
345 |
345 |
346 |
346 |
441 \end{frame} |
441 \end{frame} |
442 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
442 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
443 |
443 |
444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
444 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
445 \begin{frame}[c] |
445 \begin{frame}[c] |
446 \frametitle{Another Homework\\[-2mm] Question} |
446 \frametitle{Another Homework Question} |
447 |
447 |
448 \begin{itemize} |
448 \begin{itemize} |
449 \item How many basic regular expressions are there to match |
449 \item How many basic regular expressions are there to match |
450 the string \bl{$abcd$}\,?\pause |
450 the string \bl{$abcd$}\,?\pause |
451 \item How many if they cannot include |
451 \item How many if they cannot include |