| changeset 578 | 6e5e3adc9eb1 |
| parent 574 | bd4f144326c7 |
| child 579 | 1a521448d211 |
| 577:7a437f1f689d | 578:6e5e3adc9eb1 |
|---|---|
25 |
25 |
26 \normalsize |
26 \normalsize |
27 \begin{center} |
27 \begin{center} |
28 \begin{tabular}{ll} |
28 \begin{tabular}{ll} |
29 Email: & christian.urban at kcl.ac.uk\\ |
29 Email: & christian.urban at kcl.ac.uk\\ |
30 Office: & N7.07 (North Wing, Bush House)\\ |
30 Office: & N\liningnums{7.07} (North Wing, Bush House)\\ |
31 Slides: & KEATS (also home work is there)\\ |
31 Slides: & KEATS (also homework is there)\\ |
32 \end{tabular} |
32 \end{tabular} |
33 \end{center} |
33 \end{center} |
34 \end{frame} |
34 \end{frame} |
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
35 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
36 |
36 |
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
37 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
38 \begin{frame}[c] |
38 \begin{frame}[t] |
39 \frametitle{Regular Expressions} |
39 \frametitle{Survey: Thanks!} |
40 |
40 \small |
41 In programming languages they are often used to recognise:\medskip |
41 |
42 |
42 \hspace{9mm}{\it``\ldots Thanks a million! Thanks without end!''} |
43 \begin{itemize} |
43 |
44 \item symbols, digits |
44 \begin{textblock}{3}(12,1.7) |
45 \item identifiers |
45 \includegraphics[scale=0.1]{../pics/stickman.jpg} |
46 \item numbers (non-leading zeros) |
46 \end{textblock}\pause |
47 \item keywords |
47 |
48 \item comments |
48 \begin{textblock}{6}(1,4.15) |
49 \end{itemize}\bigskip |
49 \begin{bubble}[6.7cm] |
50 |
50 \it ``Urban is a very talented lecturer: thorough, concise, |
51 \mbox{}\hfill\bl{\url{http://www.regexper.com}} |
51 clear, and cares to make sure that we are learning!'' |
52 \end{bubble} |
|
53 \end{textblock} |
|
54 |
|
55 \only<3>{ |
|
56 \begin{textblock}{6}(0.6,8.5) |
|
57 \includegraphics[scale=0.2]{../pics/s1.png} |
|
58 \end{textblock} |
|
59 \begin{textblock}{6}(8,8.5) |
|
60 \includegraphics[scale=0.2]{../pics/s2.png} |
|
61 \end{textblock}} |
|
62 |
|
63 \only<4>{ |
|
64 \begin{textblock}{6}(0.6,8.5) |
|
65 \includegraphics[scale=0.2]{../pics/s3.png} |
|
66 \end{textblock} |
|
67 \begin{textblock}{6}(8,8.5) |
|
68 \includegraphics[scale=0.2]{../pics/s4.png} |
|
69 \end{textblock}} |
|
70 |
|
71 % \begin{itemize} |
|
72 % \item {\bf My Voice} ``lecturer speaks in a low voice and |
|
73 % is hard to hear him'' ``please use mic'' ``please use mic |
|
74 % \& lecture recording'' |
|
75 % \item {\bf Pace} ``faster pace'' ``a bit quick for me |
|
76 % personally'' |
|
77 % \item {\bf Recording} ``please use recording class'' |
|
78 % \item {\bf Module Name} ``misleading'' |
|
79 % \item {\bf Examples} ``more examples'' |
|
80 % \item {\bf Assessment} ``really appreciate extension of |
|
81 % first coursework'' |
|
82 % \end{itemize} |
|
83 |
|
84 \end{frame} |
|
85 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
86 |
|
87 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
88 \begin{frame}[c] |
|
89 |
|
90 \begin{center} |
|
91 \begin{tikzpicture}[scale=2,>=stealth',very thick, |
|
92 every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},] |
|
93 \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};} |
|
94 \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};} |
|
95 \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};} |
|
96 \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};} |
|
97 \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$}; |
|
98 \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1) |
|
99 (q1) edge[bend left] node[above] {\alert{$b$}} (q0) |
|
100 (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0) |
|
101 (q1) edge node[above] {\alert{$a$}} (q2) |
|
102 (q2) edge [loop right] node {\alert{$a$}} () |
|
103 (q0) edge [loop below] node {\alert{$b$}} () |
|
104 ; |
|
105 \end{tikzpicture} |
|
106 \end{center}\bigskip |
|
107 |
|
108 \begin{center} |
|
109 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
110 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\ |
|
111 \bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\ |
|
112 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\ |
|
113 \end{tabular} |
|
114 \end{center} |
|
115 |
|
116 |
|
117 Arden's Lemma: |
|
118 \begin{center} |
|
119 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
120 \end{center} |
|
121 |
|
122 \only<2-6>{\small |
|
123 \begin{textblock}{6}(1,0.8) |
|
124 \begin{bubble}[6.7cm] |
|
125 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
126 \multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} + \bl{$\mbox{Q}_2$}:}\\ |
|
127 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\ |
|
128 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} |
|
129 \end{tabular} |
|
130 \end{bubble} |
|
131 \end{textblock}} |
|
132 |
|
133 \only<3-6>{\small |
|
134 \begin{textblock}{6}(2,4.15) |
|
135 \begin{bubble}[6.7cm] |
|
136 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
137 \multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\ |
|
138 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ |
|
139 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$} |
|
140 \end{tabular} |
|
141 \end{bubble} |
|
142 \end{textblock}} |
|
143 |
|
144 \only<4-6>{\small |
|
145 \begin{textblock}{6}(3,7.55) |
|
146 \begin{bubble}[6.7cm] |
|
147 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
148 \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\ |
|
149 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\ |
|
150 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$} |
|
151 \end{tabular} |
|
152 \end{bubble} |
|
153 \end{textblock}} |
|
154 |
|
155 \only<5-6>{\small |
|
156 \begin{textblock}{6}(4,10.9) |
|
157 \begin{bubble}[7.5cm] |
|
158 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
159 \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\ |
|
160 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\ |
|
161 \end{tabular} |
|
162 \end{bubble} |
|
163 \end{textblock}} |
|
164 |
|
165 \only<6>{\small |
|
166 \begin{textblock}{6}(5,13.4) |
|
167 \begin{bubble}[7.5cm] |
|
168 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
169 \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\ |
|
170 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ |
|
171 \end{tabular} |
|
172 \end{bubble} |
|
173 \end{textblock}} |
|
174 |
|
175 |
|
176 \only<7->{\small |
|
177 \begin{textblock}{6}(6,11.5) |
|
178 \begin{bubble}[6.7cm] |
|
179 \begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l} |
|
180 \multicolumn{3}{@{}l}{Finally:}\\ |
|
181 \bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\ |
|
182 \bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\ |
|
183 \bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\ |
|
184 \end{tabular} |
|
185 \end{bubble} |
|
186 \end{textblock}} |
|
187 |
|
52 \end{frame} |
188 \end{frame} |
53 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
189 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
54 |
190 |
55 |
191 |
56 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
192 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
96 legend entries={Python,Ruby,my NFA}, |
232 legend entries={Python,Ruby,my NFA}, |
97 legend pos=north west, |
233 legend pos=north west, |
98 legend cell align=left] |
234 legend cell align=left] |
99 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
235 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
100 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
236 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
101 \addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; |
237 \addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; |
102 \end{axis} |
238 \end{axis} |
103 \end{tikzpicture} |
239 \end{tikzpicture} |
240 |
|
241 The punchline is that existing libraries do depth-first search in NFAs. |
|
104 |
242 |
105 \end{frame} |
243 \end{frame} |
106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
244 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
107 |
245 |
108 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
246 % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
259 \small |
397 \small |
260 for example \bl{$a^nb^n$} is not regular |
398 for example \bl{$a^nb^n$} is not regular |
261 \end{frame} |
399 \end{frame} |
262 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
400 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
263 |
401 |
402 |
|
264 |
403 |
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
404 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
266 \begin{frame}[c] |
405 \begin{frame}[c] |
267 \frametitle{Negation} |
406 \frametitle{Negation} |
268 |
407 |
303 rectangle,rounded corners=3mm, |
442 rectangle,rounded corners=3mm, |
304 very thick,draw=black!50, |
443 very thick,draw=black!50, |
305 minimum height=18mm, minimum width=20mm, |
444 minimum height=18mm, minimum width=20mm, |
306 top color=white,bottom color=black!20}] |
445 top color=white,bottom color=black!20}] |
307 |
446 |
308 \node at (3.05, 1.8) {\Large\bf Write A Compiler}; |
447 \node at (3.05, 1.8) {\Large\bf Write a compiler}; |
309 |
448 |
310 \node (0) at (-2.3,0) {}; |
449 \node (0) at (-2.3,0) {}; |
311 |
450 |
312 \node (A) at (0,0) [node] {}; |
451 \node (A) at (0,0) [node] {}; |
313 \node [below right] at (A.north west) {lexer}; |
452 \node [below right] at (A.north west) {lexer}; |
333 |
472 |
334 \end{frame} |
473 \end{frame} |
335 |
474 |
336 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
337 \begin{frame}[c] |
476 \begin{frame}[c] |
338 \frametitle{Survey: Thanks!} |
477 \frametitle{Regular Expressions} |
339 \small |
478 |
340 |
479 In programming languages they are often used to recognise:\medskip |
341 % \begin{itemize} |
480 |
342 % \item {\bf My Voice} ``lecturer speaks in a low voice and |
481 \begin{itemize} |
343 % is hard to hear him'' ``please use mic'' ``please use mic |
482 \item symbols, digits |
344 % \& lecture recording'' |
483 \item identifiers |
345 % \item {\bf Pace} ``faster pace'' ``a bit quick for me |
484 \item numbers (non-leading zeros) |
346 % personally'' |
485 \item keywords |
347 % \item {\bf Recording} ``please use recording class'' |
486 \item comments |
348 % \item {\bf Module Name} ``misleading'' |
487 \end{itemize}\bigskip |
349 % \item {\bf Examples} ``more examples'' |
488 |
350 % \item {\bf Assessment} ``really appreciate extension of |
489 \mbox{}\hfill\bl{\url{http://www.regexper.com}} |
351 % first coursework'' |
490 \end{frame} |
352 % \end{itemize} |
491 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
353 |
|
354 \end{frame} |
|
355 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
356 |
492 |
357 |
493 |
358 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
494 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
359 \begin{frame}[c] |
495 \begin{frame}[c] |
360 \frametitle{Lexing: Test Case} |
496 \frametitle{Lexing: Test Case} |
362 \mbox{\lstinputlisting[language=While]{../progs/fib.while}} |
498 \mbox{\lstinputlisting[language=While]{../progs/fib.while}} |
363 |
499 |
364 \end{frame} |
500 \end{frame} |
365 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
501 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
366 |
502 |
367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
368 \begin{frame}[c] |
504 %\begin{frame}[c] |
369 \frametitle{?? Test Case} |
505 %\frametitle{?? Test Case} |
370 |
506 % |
371 \mbox{\lstinputlisting[language=While]{../progs/collatz.while}} |
507 %\mbox{\lstinputlisting[language=While]{../progs/collatz.while}} |
372 |
508 % |
373 \end{frame} |
509 %\end{frame} |
374 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
375 |
511 |
376 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
512 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
377 \begin{frame}[t] |
513 \begin{frame}[t] |
378 |
514 |
442 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
578 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
443 \begin{frame}[c] |
579 \begin{frame}[c] |
444 |
580 |
445 |
581 |
446 There is one small problem with the tokenizer. How should we |
582 There is one small problem with the tokenizer. How should we |
447 tokenize: |
583 tokenize\ldots? |
448 |
584 |
449 \begin{center} |
585 \begin{center} |
450 \large\code{"x-3"} |
586 \large\code{"x-3"} |
451 \end{center} |
587 \end{center} |
452 |
588 |
476 |
612 |
477 Or, keywords are \pcode{if} and identifiers are |
613 Or, keywords are \pcode{if} and identifiers are |
478 letters followed by ``letters + numbers + \_''$^*$ |
614 letters followed by ``letters + numbers + \_''$^*$ |
479 |
615 |
480 \[ |
616 \[ |
481 \bl{iffoo} |
617 \bl{if}\qquad\bl{iffoo} |
482 \] |
618 \] |
483 |
619 |
484 \end{frame} |
620 \end{frame} |
485 |
621 |
486 |
622 |
574 & & \bl{$Empty$} \\ |
710 & & \bl{$Empty$} \\ |
575 & \bl{$\mid$} & \bl{$Char(c)$} \\ |
711 & \bl{$\mid$} & \bl{$Char(c)$} \\ |
576 & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ |
712 & \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\ |
577 & \bl{$\mid$} & \bl{$Left(v)$} \\ |
713 & \bl{$\mid$} & \bl{$Left(v)$} \\ |
578 & \bl{$\mid$} & \bl{$Right(v)$} \\ |
714 & \bl{$\mid$} & \bl{$Right(v)$} \\ |
579 & \bl{$\mid$} & \bl{$[]$} \\ |
715 & \bl{$\mid$} & \bl{$Stars\,[]$} \\ |
580 & \bl{$\mid$} & \bl{$[v_1,\ldots\,v_n]$} \\ |
716 & \bl{$\mid$} & \bl{$Stars\,[v_1,\ldots\,v_n]$} \\ |
581 \end{tabular} |
717 \end{tabular} |
582 \end{column} |
718 \end{column} |
583 \end{columns} |
719 \end{columns} |
584 \end{center} |
720 \end{center} |
585 |
721 |
608 \bl{$mkeps\,(\ONE)$} & \bl{$\dn$} & \bl{$Empty$}\\ |
744 \bl{$mkeps\,(\ONE)$} & \bl{$\dn$} & \bl{$Empty$}\\ |
609 \bl{$mkeps\,(r_1 + r_2)$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
745 \bl{$mkeps\,(r_1 + r_2)$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
610 & & \bl{then $Left(mkeps(r_1))$}\\ |
746 & & \bl{then $Left(mkeps(r_1))$}\\ |
611 & & \bl{else $Right(mkeps(r_2))$}\\ |
747 & & \bl{else $Right(mkeps(r_2))$}\\ |
612 \bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ |
748 \bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ |
613 \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$[]$} \\ |
749 \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$Stars\,[]$} \\ |
614 \end{tabular} |
750 \end{tabular} |
615 \end{center} |
751 \end{center} |
616 |
752 |
617 \end{frame} |
753 \end{frame} |
618 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
754 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
622 \frametitle{Inject} |
758 \frametitle{Inject} |
623 |
759 |
624 Injecting (``Adding'') a character to a value\\[-12mm]\mbox{} |
760 Injecting (``Adding'') a character to a value\\[-12mm]\mbox{} |
625 |
761 |
626 \begin{center} |
762 \begin{center} |
627 \begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} |
763 \begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}} |
628 \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\ |
764 \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\ |
629 \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ |
765 \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\ |
630 \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ |
766 \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\ |
631 \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
767 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
632 \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
768 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\ |
633 \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ |
769 \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\ |
634 \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\ |
770 \bl{$inj\,(r^*)\,c\,(Seq(v,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\ |
635 \end{tabular} |
771 \end{tabular} |
636 \end{center}\bigskip |
772 \end{center}\bigskip |
637 |
773 |
638 \footnotesize |
774 \footnotesize |
639 \bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value |
775 \bl{$inj$}: 1st arg $\mapsto$ a rexp; 2nd arg $\mapsto$ a character; 3rd arg $\mapsto$ a value |
907 \begin{frame}[c] |
1043 \begin{frame}[c] |
908 \frametitle{Simplification} |
1044 \frametitle{Simplification} |
909 |
1045 |
910 \begin{itemize} |
1046 \begin{itemize} |
911 \item If we simplify after the derivative, then we are building the |
1047 \item If we simplify after the derivative, then we are building the |
912 value for the simplified regular expression, but \emph{not} for the original |
1048 value for the simplified regular expression, but \alert{\textbf{not}} for the original |
913 regular expression. |
1049 regular expression. |
914 \end{itemize} |
1050 \end{itemize} |
915 |
1051 |
916 \begin{center} |
1052 \begin{center} |
917 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
1053 \begin{tikzpicture}[scale=2,node distance=1.3cm,every node/.style={minimum size=8mm}] |
954 \begin{center} |
1090 \begin{center} |
955 \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$} |
1091 \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$} |
956 \end{center} |
1092 \end{center} |
957 |
1093 |
958 and answer how this regular expression matches the empty string |
1094 and answer how this regular expression matches the empty string |
1095 with the value |
|
959 |
1096 |
960 \begin{center} |
1097 \begin{center} |
961 \bl{$Right(Right(Empty))$} |
1098 \bl{$Right(Right(Empty))$} |
962 \end{center}\bigskip |
1099 \end{center}\bigskip |
963 |
1100 |
964 But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$}. |
1101 But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$} (see \textit{mkeps}). |
965 |
1102 |
966 \end{frame} |
1103 \end{frame} |
967 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1104 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
968 |
1105 |
969 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1197 \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\ |
1334 \bl{$env(Empty)$} & \bl{$\dn$} & \bl{$[]$}\\ |
1198 \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\ |
1335 \bl{$env(Char(c))$} & \bl{$\dn$} & \bl{$[]$}\\ |
1199 \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ |
1336 \bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ |
1200 \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ |
1337 \bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\ |
1201 \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\ |
1338 \bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\ |
1202 \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} & |
1339 \bl{$env(Stars\,[v_1,\ldots ,v_n])$} & \bl{$\dn$} & |
1203 \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\ |
1340 \bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\ |
1204 \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\ |
1341 \bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\ |
1205 \end{tabular} |
1342 \end{tabular} |
1206 \end{center} |
1343 \end{center} |
1207 |
1344 |
1299 |
1436 |
1300 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1437 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1301 \begin{frame}[c] |
1438 \begin{frame}[c] |
1302 \begin{center} |
1439 \begin{center} |
1303 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
1440 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
1304 \bl{$zeroable(\varnothing)$} & \bl{$\dn$} & \bl{$true$}\\ |
1441 \bl{$zeroable(\ZERO)$} & \bl{$\dn$} & \bl{$true$}\\ |
1305 \bl{$zeroable(\epsilon)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1442 \bl{$zeroable(\ONE)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1306 \bl{$zeroable(c)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1443 \bl{$zeroable(c)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1307 \bl{$zeroable(r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\ |
1444 \bl{$zeroable(r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\ |
1308 \bl{$zeroable(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\ |
1445 \bl{$zeroable(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\ |
1309 \bl{$zeroable(r^*)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1446 \bl{$zeroable(r^*)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1310 \end{tabular} |
1447 \end{tabular} |