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 \begin{tabular}{@{}cc@{}} |
55 \begin{tabular}{@{}cc@{}} |
55 \begin{tikzpicture} |
56 \begin{tikzpicture} |
56 \begin{axis}[ |
57 \begin{axis}[ |
57 xlabel={\pcode{a}s}, |
58 xlabel={$n$}, |
|
59 x label style={at={(1.05,0.0)}}, |
58 ylabel={time in secs}, |
60 ylabel={time in secs}, |
59 enlargelimits=false, |
61 enlargelimits=false, |
60 xtick={0,5,...,30}, |
62 xtick={0,5,...,30}, |
61 xmax=30, |
63 xmax=33, |
62 ymax=35, |
64 ymax=35, |
63 ytick={0,5,...,30}, |
65 ytick={0,5,...,30}, |
64 scaled ticks=false, |
66 scaled ticks=false, |
65 axis lines=left, |
67 axis lines=left, |
66 width=4.5cm, |
68 width=5cm, |
67 height=4.5cm, |
69 height=4.5cm, |
68 legend entries={Python,Ruby}, |
70 legend entries={Python,Ruby}, |
69 legend pos=north west, |
71 legend pos=north west, |
70 legend cell align=left |
72 legend cell align=left |
71 ] |
73 ] |
72 \addplot[blue,mark=*, mark options={fill=white}] |
74 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
73 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}] |
|
75 table {re-ruby.data}; |
|
76 \end{axis} |
76 \end{axis} |
77 \end{tikzpicture} |
77 \end{tikzpicture} |
78 & |
78 & |
79 \begin{tikzpicture} |
79 \begin{tikzpicture} |
80 \begin{axis}[ |
80 \begin{axis}[ |
81 xlabel={\pcode{a}s}, |
81 xlabel={$n$}, |
|
82 x label style={at={(1.1,0.05)}}, |
82 ylabel={time in secs}, |
83 ylabel={time in secs}, |
83 enlargelimits=false, |
84 enlargelimits=false, |
84 xtick={0,3000,...,12000}, |
85 xtick={0,4000,...,12000}, |
85 xmax=12000, |
86 xmax=13500, |
86 ymax=35, |
87 ymax=35, |
87 ytick={0,5,...,30}, |
88 ytick={0,5,...,30}, |
88 scaled ticks=false, |
89 scaled ticks=false, |
89 axis lines=left, |
90 axis lines=left, |
90 width=5.5cm, |
91 width=5cm, |
91 height=4.5cm |
92 height=4.5cm |
92 ] |
93 ] |
93 \addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; |
94 \addplot[green,mark=square*,mark options={fill=white}] table {re2.data}; |
94 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
95 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
95 \end{axis} |
96 \end{axis} |
96 \end{tikzpicture} |
97 \end{tikzpicture} |
97 \end{tabular} |
98 \end{tabular} |
98 \end{center} |
99 \end{center} |
99 |
100 |
100 |
101 \small |
101 \end{frame} |
102 In the handouts is a similar graph with \bl{$(a^*)^* \cdot b$} for Java. |
102 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
103 |
|
104 \end{frame} |
|
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
103 |
106 |
104 |
107 |
105 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
108 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
106 \begin{frame}[c] |
109 \begin{frame}[c] |
107 \frametitle{Languages} |
110 \frametitle{Languages} |
108 |
111 |
109 \begin{itemize} |
112 \begin{itemize} |
110 |
113 |
111 \item A \alert{\bf language} is a set of strings, for example\medskip |
114 \item A \alert{\bf Language} is a set of strings, for example\medskip |
112 \begin{center} |
115 \begin{center} |
113 \bl{$\{[], hello, \textit{foobar}, a, abc\}$} |
116 \bl{$\{[], hello, \textit{foobar}, a, abc\}$} |
114 \end{center}\bigskip |
117 \end{center}\bigskip |
115 |
118 |
116 \item \alert{\bf Concatenation} of strings and languages |
119 \item \alert{\bf Concatenation} of strings and languages |
226 \item The \alert{\bf Semantic Derivative} of a |
229 \item The \alert{\bf Semantic Derivative} of a |
227 \underline{language}\\ wrt to a character \bl{$c$}: |
230 \underline{language}\\ wrt to a character \bl{$c$}: |
228 \bigskip |
231 \bigskip |
229 |
232 |
230 \begin{center} |
233 \begin{center} |
231 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
234 \bl{$\Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
232 \end{center}\bigskip\bigskip\bigskip |
235 \end{center}\bigskip\bigskip\bigskip |
233 |
236 |
234 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then |
237 For \bl{$A = \{\textit{foo}, \textit{bar}, \textit{frak}\}$} then |
235 |
238 |
236 \begin{center} |
239 \begin{center} |
237 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
240 \bl{\begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l} |
238 $Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\ |
241 $\Der\,f\,A$ & $=$ & $\{\textit{oo}, \textit{rak}\}$\\ |
239 $Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\ |
242 $\Der\,b\,A$ & $=$ & $\{\textit{ar}\}$\\ |
240 $Der\,a\,A$ & $=$ & $\{\}$\\\pause |
243 $\Der\,a\,A$ & $=$ & $\{\}$\\\pause |
241 \end{tabular}} |
244 \end{tabular}} |
242 \end{center} |
245 \end{center} |
243 |
246 |
244 \small |
247 \small |
245 We can extend this definition to strings |
248 We can extend this definition to strings |
246 \[ |
249 \[ |
247 \bl{Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}} |
250 \bl{\Ders\,s\,A = \{s'\;|\;s\,@\,s' \in A\}} |
248 \] |
251 \] |
249 |
252 |
250 \end{itemize} |
253 \end{itemize} |
251 |
254 |
252 \end{frame} |
255 \end{frame} |
402 \end{frame} |
405 \end{frame} |
403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
406 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
404 |
407 |
405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
408 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
406 \begin{frame}[c] |
409 \begin{frame}[c] |
407 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
410 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} and \bl{$(a^*)^* \cdot b$}} |
408 |
411 |
409 \begin{center} |
412 \begin{center}\footnotesize |
|
413 \begin{tabular}{@{}c@{\hspace{-2mm}}c@{}} |
410 \begin{tikzpicture} |
414 \begin{tikzpicture} |
411 \begin{axis}[ |
415 \begin{axis}[ |
412 xlabel={\pcode{a}s}, |
416 xlabel={$n$}, |
|
417 x label style={at={(1.05,0.0)}}, |
413 ylabel={time in secs}, |
418 ylabel={time in secs}, |
414 enlargelimits=false, |
419 enlargelimits=false, |
415 xtick={0,5,...,30}, |
420 xtick={0,5,...,30}, |
416 xmax=30, |
421 xmax=33, |
417 ymax=35, |
422 ymax=35, |
418 ytick={0,5,...,30}, |
423 ytick={0,5,...,30}, |
419 scaled ticks=false, |
424 scaled ticks=false, |
420 axis lines=left, |
425 axis lines=left, |
421 width=9cm, |
426 width=5.5cm, |
422 height=7cm, |
427 height=4.5cm, |
423 legend entries={Python,Ruby}, |
428 legend entries={Python,Ruby}, |
424 legend pos=north west, |
429 legend pos=north west, |
425 legend cell align=left |
430 legend cell align=left |
426 ] |
431 ] |
427 \addplot[blue,mark=*, mark options={fill=white}] |
432 \addplot[blue,mark=*, mark options={fill=white}] |
428 table {re-python.data}; |
433 table {re-python.data}; |
429 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
434 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
430 table {re-ruby.data}; |
435 table {re-ruby.data}; |
431 \end{axis} |
436 \end{axis} |
432 \end{tikzpicture} |
437 \end{tikzpicture} |
|
438 & |
|
439 \begin{tikzpicture} |
|
440 \begin{axis}[ |
|
441 xlabel={$n$}, |
|
442 x label style={at={(1.05,0.0)}}, |
|
443 ylabel={time in secs}, |
|
444 enlargelimits=false, |
|
445 xtick={0,5,...,30}, |
|
446 xmax=33, |
|
447 ymax=35, |
|
448 ytick={0,5,...,30}, |
|
449 scaled ticks=false, |
|
450 axis lines=left, |
|
451 width=5.5cm, |
|
452 height=4.5cm, |
|
453 legend entries={Java}, |
|
454 legend pos=north west, |
|
455 legend cell align=left] |
|
456 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data}; |
|
457 \end{axis} |
|
458 \end{tikzpicture} |
|
459 \end{tabular} |
433 \end{center} |
460 \end{center} |
434 |
461 |
435 \end{frame} |
462 \end{frame} |
436 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
463 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
437 |
464 |
442 \begin{itemize} |
469 \begin{itemize} |
443 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
470 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip |
444 \item Evil regular expressions\medskip |
471 \item Evil regular expressions\medskip |
445 \begin{itemize} |
472 \begin{itemize} |
446 \item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} |
473 \item \bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$} |
447 \item \bl{$(a^+)^+$} |
474 \item \bl{$(a^*)^*$} |
448 \item \bl{$([a$\,-\,$z]^+)^*$} |
475 \item \bl{$([a$\,-\,$z]^+)^*$} |
449 \item \bl{$(a + a \cdot a)^+$} |
476 \item \bl{$(a + a \cdot a)^*$} |
450 \item \bl{$(a + a?)^+$} |
477 \item \bl{$(a + a?)^*$} |
451 \end{itemize} |
478 \end{itemize} |
452 \end{itemize} |
479 \end{itemize} |
453 |
480 |
454 \end{frame} |
481 \end{frame} |
455 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
482 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
482 \large |
509 \large |
483 If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular |
510 If \bl{$r$} matches the string \bl{$c\!::\!s$}, what is a regular |
484 expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip |
511 expression that matches just \bl{$s$}?\bigskip\bigskip\bigskip\bigskip |
485 |
512 |
486 \small |
513 \small |
487 \bl{$der\,c\,r$} gives the answer, Brzozowski 1964 |
514 \bl{$\der\,c\,r$} gives the answer, Brzozowski 1964 |
488 \end{frame} |
515 \end{frame} |
489 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
490 |
517 |
491 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
492 \begin{frame}[c] |
519 \begin{frame}[c] |
493 \frametitle{The Derivative of a Rexp} |
520 \frametitle{The Derivative of a Rexp} |
494 |
521 |
495 \begin{center} |
522 \begin{center} |
496 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
523 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
497 \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
524 \bl{$\der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
498 \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
525 \bl{$\der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\ |
499 \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\ |
526 \bl{$\der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\ |
500 \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\ |
527 \bl{$\der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$\der\, c\, r_1 + \der\, c\, r_2$} & \\ |
501 \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
528 \bl{$\der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\ |
502 & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\ |
529 & & \bl{then $(\der\,c\,r_1) \cdot r_2 + \der\, c\, r_2$}\\ |
503 & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\ |
530 & & \bl{else $(\der\, c\, r_1) \cdot r_2$}\\ |
504 \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\bigskip\\\pause |
531 \bl{$\der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\bigskip\\\pause |
505 |
532 |
506 \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
533 \bl{$\ders\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\ |
507 \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\ |
534 \bl{$\ders\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\ders\,s\,(\der\,c\,r)$} & \\ |
508 \end{tabular} |
535 \end{tabular} |
509 \end{center} |
536 \end{center} |
510 |
537 |
511 \end{frame} |
538 \end{frame} |
512 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
539 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
531 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
558 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
532 \begin{frame}[c] |
559 \begin{frame}[c] |
533 \frametitle{The Algorithm} |
560 \frametitle{The Algorithm} |
534 |
561 |
535 \begin{center} |
562 \begin{center} |
536 \begin{tabular}{l} |
563 \begin{tabular}{l} |
537 \bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\textit{ders}\,r\,s)$} |
564 \bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\,r\,s)$} |
538 \end{tabular} |
565 \end{tabular} |
539 \end{center} |
566 \end{center} |
540 |
567 |
541 |
568 |
542 \end{frame} |
569 \end{frame} |
543 %%%%%%%%%%%%%%%%% |
570 %%%%%%%%%%%%%%%%% |
544 |
571 |
545 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
572 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
546 \begin{frame}[t] |
573 \begin{frame}[t] |
547 \frametitle{The Algorithm} |
574 \frametitle{An Example} |
548 |
575 |
549 \begin{center} |
576 Does \bl{$r_1$} match \bl{$abc$}? |
550 \begin{tabular}{@{}rll@{}} |
577 \begin{center} |
551 Input: & \bl{$r_1$}, \bl{$abc$}\medskip\\ |
578 \begin{tabular}{@{}rl@{}l@{}} |
552 Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = der\,a\,r_1)$}\smallskip\\ |
579 Step 1: & build derivative of \bl{$a$} and \bl{$r_1$} & \bl{$(r_2 = \der\,a\,r_1)$}\smallskip\\ |
553 Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = der\,b\,r_2)$}\smallskip\\ |
580 Step 2: & build derivative of \bl{$b$} and \bl{$r_2$} & \bl{$(r_3 = \der\,b\,r_2)$}\smallskip\\ |
554 Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = der\,b\,r_3)$}\smallskip\\ |
581 Step 3: & build derivative of \bl{$c$} and \bl{$r_3$} & \bl{$(r_4 = \der\,c\,r_3)$}\smallskip\\ |
555 Step 4: & the string is exhausted; test & (\bl{$nullable(r_4)$})\\ |
582 Step 4: & the string is exhausted: & \bl{($nullable(r_4))$}\\ |
556 & whether \bl{$r_4$} can recognise\\ |
583 & test whether \bl{$r_4$} can recognise\\ |
557 & the empty string\smallskip\\ |
584 & the empty string\smallskip\\ |
558 Output: & result of the test\\ |
585 Output: & result of the test\\ |
559 & $\Rightarrow \bl{\textit{true}} \,\text{or}\, |
586 & $\Rightarrow \bl{\textit{true}} \,\text{or}\, |
560 \bl{\textit{false}}$\\ |
587 \bl{\textit{false}}$\\ |
561 \end{tabular} |
588 \end{tabular} |
571 |
598 |
572 If we want to recognise the string \bl{$abc$} with regular |
599 If we want to recognise the string \bl{$abc$} with regular |
573 expression \bl{$r_1$} then\medskip |
600 expression \bl{$r_1$} then\medskip |
574 |
601 |
575 \begin{enumerate} |
602 \begin{enumerate} |
576 \item \bl{$Der\,a\,(L(r_1))$}\pause |
603 \item \bl{$\Der\,a\,(L(r_1))$}\pause |
577 \item \bl{$Der\,b\,(Der\,a\,(L(r_1)))$}\pause |
604 \item \bl{$\Der\,b\,(\Der\,a\,(L(r_1)))$}\pause |
578 \item \bl{$Der\,c\,(Der\,b\,(Der\,a\,(L(r_1))))$}\bigskip |
605 \item \bl{$\Der\,c\,(\Der\,b\,(\Der\,a\,(L(r_1))))$}\bigskip |
579 \item finally we test whether the empty string is in this |
606 \item finally we test whether the empty string is in this |
580 set; same for \bl{$Ders\,abc\,(L(r_1))$}.\medskip |
607 set; same for \bl{$\Ders\,abc\,(L(r_1))$}.\medskip |
581 \end{enumerate} |
608 \end{enumerate} |
582 |
609 |
583 The matching algorithm works similarly, just over regular expressions instead of sets. |
610 The matching algorithm works similarly, just over regular expressions instead of sets. |
584 \end{frame} |
611 \end{frame} |
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
612 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
586 |
613 |
587 |
614 |
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
615 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
589 \begin{frame}[c] |
616 \begin{frame}[c] |
590 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
617 \frametitle{Oops\ldots\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
591 |
618 |
592 \begin{center} |
619 \begin{center} |
593 \begin{tikzpicture} |
620 \begin{tikzpicture} |
594 \begin{axis}[ |
621 \begin{axis}[ |
595 xlabel={\pcode{a}s}, |
622 xlabel={$n$}, |
|
623 x label style={at={(1.05,0.0)}}, |
596 ylabel={time in secs}, |
624 ylabel={time in secs}, |
597 enlargelimits=false, |
625 enlargelimits=false, |
598 xtick={0,5,...,30}, |
626 xtick={0,5,...,30}, |
599 xmax=30, |
627 xmax=31, |
600 ytick={0,5,...,30}, |
628 ytick={0,5,...,30}, |
601 scaled ticks=false, |
629 scaled ticks=false, |
602 axis lines=left, |
630 axis lines=left, |
603 width=7cm, |
631 width=7cm, |
604 height=7cm, |
632 height=7cm, |
705 |
735 |
706 Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with |
736 Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with |
707 |
737 |
708 \begin{center} |
738 \begin{center} |
709 \begin{tabular}{l} |
739 \begin{tabular}{l} |
710 \bl{$der\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$}\\ |
740 \bl{$\der\,a\,r = ((\ONE \cdot b) + \ZERO) \cdot r$}\\ |
711 \bl{$der\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$}\\ |
741 \bl{$\der\,b\,r = ((\ZERO \cdot b) + \ONE)\cdot r$}\\ |
712 \bl{$der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$} |
742 \bl{$\der\,c\,r = ((\ZERO \cdot b) + \ZERO)\cdot r$} |
713 \end{tabular} |
743 \end{tabular} |
714 \end{center} |
744 \end{center} |
715 |
745 |
716 What are these regular expressions equivalent to? |
746 What are these regular expressions equivalent to? |
717 |
747 |
718 \end{frame} |
748 \end{frame} |
719 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
749 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
720 |
|
721 |
750 |
722 |
751 |
723 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
752 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
724 \begin{frame}[t] |
753 \begin{frame}[t] |
725 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
754 \frametitle{\bl{$(a^{?\{n\}}) \cdot a^{\{n\}}$}} |
726 |
755 |
727 \begin{center} |
756 \begin{center} |
728 \begin{tikzpicture} |
757 \begin{tikzpicture} |
729 \begin{axis}[ |
758 \begin{axis}[ |
730 xlabel={\pcode{a}s}, |
759 xlabel={$n$}, |
|
760 x label style={at={(1.05,0.0)}}, |
731 ylabel={time in secs}, |
761 ylabel={time in secs}, |
732 enlargelimits=false, |
762 enlargelimits=false, |
733 xtick={0,3000,...,12000}, |
763 xtick={0,3000,...,12000}, |
734 xmax=12000, |
764 xmax=14000, |
735 ymax=35, |
765 ymax=35, |
736 ytick={0,5,...,30}, |
766 ytick={0,5,...,30}, |
737 scaled ticks=false, |
767 scaled ticks=false, |
738 axis lines=left, |
768 axis lines=left, |
739 width=9cm, |
769 width=9cm, |
740 height=7cm |
770 height=7cm, |
|
771 legend entries={Scala V2,Scala V3}, |
|
772 legend pos=north east |
741 ] |
773 ] |
742 \addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; |
774 \addplot[green,mark=square*,mark options={fill=white}] table {re2b.data}; |
743 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
775 \addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
744 \end{axis} |
776 \end{axis} |
745 \end{tikzpicture} |
777 \end{tikzpicture} |
746 \end{center} |
778 \end{center} |
747 |
779 |
748 \end{frame} |
780 \end{frame} |
749 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
781 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
782 |
|
783 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
784 \begin{frame}[c] |
|
785 \frametitle{\bl{$(a^*)^* \cdot b$}} |
|
786 |
|
787 \begin{center} |
|
788 \begin{tikzpicture} |
|
789 \begin{axis}[ |
|
790 xlabel={$n$}, |
|
791 x label style={at={(1.09,0.0)}}, |
|
792 ylabel={time in secs}, |
|
793 enlargelimits=false, |
|
794 xmax=5000, |
|
795 xtick={0,2000,...,6000}, |
|
796 ytick={0,5,...,10}, |
|
797 ymax=15, |
|
798 scaled ticks=false, |
|
799 axis lines=left, |
|
800 width=9cm, |
|
801 height=5cm, |
|
802 legend entries={Scala V3}, |
|
803 legend pos=north west, |
|
804 legend cell align=left] |
|
805 \addplot[green,mark=square*,mark options={fill=white}] table {re2a.data}; |
|
806 %%where is 2nd graph |
|
807 %%\addplot[black,mark=square*,mark options={fill=white}] table {re3.data}; |
|
808 \end{axis} |
|
809 \end{tikzpicture} |
|
810 \end{center} |
|
811 |
|
812 \end{frame} |
|
813 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
814 |
|
815 |
750 |
816 |
751 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
817 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
752 \begin{frame}[t] |
818 \begin{frame}[t] |
753 \frametitle{What is good about this Alg.} |
819 \frametitle{What is good about this Alg.} |
754 |
820 |
855 \item We started from |
921 \item We started from |
856 |
922 |
857 \begin{center} |
923 \begin{center} |
858 \begin{tabular}{rp{4cm}} |
924 \begin{tabular}{rp{4cm}} |
859 & \bl{$s \in L(r)$}\medskip\\ |
925 & \bl{$s \in L(r)$}\medskip\\ |
860 \bl{$\Leftrightarrow$} & \bl{$[] \in Ders\,s\,(L(r))$}\pause |
926 \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause |
861 \end{tabular} |
927 \end{tabular} |
862 \end{center} |
928 \end{center} |
863 |
929 |
864 \item if we can show \bl{$Ders\, s\,(L(r)) = L(ders\,s\,r)$} we |
930 \item if we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we |
865 have |
931 have |
866 |
932 |
867 \begin{center} |
933 \begin{center} |
868 \begin{tabular}{rp{4cm}} |
934 \begin{tabular}{rp{4cm}} |
869 \bl{$\Leftrightarrow$} & \bl{$[] \in L(ders\,s\,r)$}\medskip\\ |
935 \bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\ |
870 \bl{$\Leftrightarrow$} & \bl{$nullable(ders\,s\,r)$}\medskip\\ |
936 \bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\ |
871 \bl{$\dn$} & \bl{$matches\,s\,r$} |
937 \bl{$\dn$} & \bl{$matches\,s\,r$} |
872 \end{tabular} |
938 \end{tabular} |
873 \end{center} |
939 \end{center} |
874 |
940 |
875 \end{itemize} |
941 \end{itemize} |
882 \frametitle{Proofs about Rexp (5)} |
948 \frametitle{Proofs about Rexp (5)} |
883 |
949 |
884 Let \bl{$Der\,c\,A$} be the set defined as |
950 Let \bl{$Der\,c\,A$} be the set defined as |
885 |
951 |
886 \begin{center} |
952 \begin{center} |
887 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
953 \bl{$\Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
888 \end{center} |
954 \end{center} |
889 |
955 |
890 We can prove |
956 We can prove |
891 |
957 |
892 \begin{center} |
958 \begin{center} |
893 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
959 \bl{$L(\der\,c\,r) = \Der\,c\,(L(r))$} |
894 \end{center} |
960 \end{center} |
895 |
961 |
896 by induction on \bl{$r$}. |
962 by induction on \bl{$r$}. |
897 |
963 |
898 \end{frame} |
964 \end{frame} |