|
1 \documentclass[dvipsnames,14pt,t]{beamer} |
|
2 \usepackage{beamerthemeplainculight} |
|
3 \usepackage[T1]{fontenc} |
|
4 \usepackage[latin1]{inputenc} |
|
5 \usepackage{mathpartir} |
|
6 \usepackage[absolute,overlay]{textpos} |
|
7 \usepackage{ifthen} |
|
8 \usepackage{tikz} |
|
9 \usepackage{pgf} |
|
10 \usepackage{calc} |
|
11 \usepackage{ulem} |
|
12 \usepackage{courier} |
|
13 \usepackage{listings} |
|
14 \renewcommand{\uline}[1]{#1} |
|
15 \usetikzlibrary{arrows} |
|
16 \usetikzlibrary{automata} |
|
17 \usetikzlibrary{shapes} |
|
18 \usetikzlibrary{shadows} |
|
19 \usetikzlibrary{positioning} |
|
20 \usetikzlibrary{calc} |
|
21 \usetikzlibrary{plotmarks} |
|
22 \usepackage{graphicx} |
|
23 |
|
24 \definecolor{javared}{rgb}{0.6,0,0} % for strings |
|
25 \definecolor{javagreen}{rgb}{0.25,0.5,0.35} % comments |
|
26 \definecolor{javapurple}{rgb}{0.5,0,0.35} % keywords |
|
27 \definecolor{javadocblue}{rgb}{0.25,0.35,0.75} % javadoc |
|
28 |
|
29 \lstset{language=Java, |
|
30 basicstyle=\ttfamily, |
|
31 keywordstyle=\color{javapurple}\bfseries, |
|
32 stringstyle=\color{javagreen}, |
|
33 commentstyle=\color{javagreen}, |
|
34 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
35 numbers=left, |
|
36 numberstyle=\tiny\color{black}, |
|
37 stepnumber=1, |
|
38 numbersep=10pt, |
|
39 tabsize=2, |
|
40 showspaces=false, |
|
41 showstringspaces=false} |
|
42 |
|
43 \lstdefinelanguage{scala}{ |
|
44 morekeywords={abstract,case,catch,class,def,% |
|
45 do,else,extends,false,final,finally,% |
|
46 for,if,implicit,import,match,mixin,% |
|
47 new,null,object,override,package,% |
|
48 private,protected,requires,return,sealed,% |
|
49 super,this,throw,trait,true,try,% |
|
50 type,val,var,while,with,yield}, |
|
51 otherkeywords={=>,<-,<\%,<:,>:,\#,@}, |
|
52 sensitive=true, |
|
53 morecomment=[l]{//}, |
|
54 morecomment=[n]{/*}{*/}, |
|
55 morestring=[b]", |
|
56 morestring=[b]', |
|
57 morestring=[b]""" |
|
58 } |
|
59 |
|
60 \lstset{language=Scala, |
|
61 basicstyle=\ttfamily, |
|
62 keywordstyle=\color{javapurple}\bfseries, |
|
63 stringstyle=\color{javagreen}, |
|
64 commentstyle=\color{javagreen}, |
|
65 morecomment=[s][\color{javadocblue}]{/**}{*/}, |
|
66 numbers=left, |
|
67 numberstyle=\tiny\color{black}, |
|
68 stepnumber=1, |
|
69 numbersep=10pt, |
|
70 tabsize=2, |
|
71 showspaces=false, |
|
72 showstringspaces=false} |
|
73 |
|
74 % beamer stuff |
|
75 \renewcommand{\slidecaption}{AFL 06, King's College London, 31.~October 2012} |
|
76 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
|
77 \newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions |
|
78 |
|
79 |
|
80 % The data files, written on the first run. |
|
81 \begin{filecontents}{re-python.data} |
|
82 1 0.029 |
|
83 5 0.029 |
|
84 10 0.029 |
|
85 15 0.032 |
|
86 16 0.042 |
|
87 17 0.042 |
|
88 18 0.055 |
|
89 19 0.084 |
|
90 20 0.136 |
|
91 21 0.248 |
|
92 22 0.464 |
|
93 23 0.899 |
|
94 24 1.773 |
|
95 25 3.505 |
|
96 26 6.993 |
|
97 27 14.503 |
|
98 28 29.307 |
|
99 #29 58.886 |
|
100 \end{filecontents} |
|
101 |
|
102 \begin{filecontents}{re1.data} |
|
103 1 0.00179 |
|
104 2 0.00011 |
|
105 3 0.00014 |
|
106 4 0.00026 |
|
107 5 0.00050 |
|
108 6 0.00095 |
|
109 7 0.00190 |
|
110 8 0.00287 |
|
111 9 0.00779 |
|
112 10 0.01399 |
|
113 11 0.01894 |
|
114 12 0.03666 |
|
115 13 0.07994 |
|
116 14 0.08944 |
|
117 15 0.02377 |
|
118 16 0.07392 |
|
119 17 0.22798 |
|
120 18 0.65310 |
|
121 19 2.11360 |
|
122 20 6.31606 |
|
123 21 21.46013 |
|
124 \end{filecontents} |
|
125 |
|
126 \begin{filecontents}{re2.data} |
|
127 1 0.00240 |
|
128 2 0.00013 |
|
129 3 0.00020 |
|
130 4 0.00030 |
|
131 5 0.00049 |
|
132 6 0.00083 |
|
133 7 0.00146 |
|
134 8 0.00228 |
|
135 9 0.00351 |
|
136 10 0.00640 |
|
137 11 0.01217 |
|
138 12 0.02565 |
|
139 13 0.01382 |
|
140 14 0.02423 |
|
141 15 0.05065 |
|
142 16 0.06522 |
|
143 17 0.02140 |
|
144 18 0.05176 |
|
145 19 0.18254 |
|
146 20 0.51898 |
|
147 21 1.39631 |
|
148 22 2.69501 |
|
149 23 8.07952 |
|
150 \end{filecontents} |
|
151 |
|
152 \begin{filecontents}{re-internal.data} |
|
153 1 0.00069 |
|
154 301 0.00700 |
|
155 601 0.00297 |
|
156 901 0.00470 |
|
157 1201 0.01301 |
|
158 1501 0.01175 |
|
159 1801 0.01761 |
|
160 2101 0.01787 |
|
161 2401 0.02717 |
|
162 2701 0.03932 |
|
163 3001 0.03470 |
|
164 3301 0.04349 |
|
165 3601 0.05411 |
|
166 3901 0.06181 |
|
167 4201 0.07119 |
|
168 4501 0.08578 |
|
169 \end{filecontents} |
|
170 |
|
171 \begin{filecontents}{re3.data} |
|
172 1 0.001605 |
|
173 501 0.131066 |
|
174 1001 0.057885 |
|
175 1501 0.136875 |
|
176 2001 0.176238 |
|
177 2501 0.254363 |
|
178 3001 0.37262 |
|
179 3501 0.500946 |
|
180 4001 0.638384 |
|
181 4501 0.816605 |
|
182 5001 1.00491 |
|
183 5501 1.232505 |
|
184 6001 1.525672 |
|
185 6501 1.757502 |
|
186 7001 2.092784 |
|
187 7501 2.429224 |
|
188 8001 2.803037 |
|
189 8501 3.463045 |
|
190 9001 3.609 |
|
191 9501 4.081504 |
|
192 10001 4.54569 |
|
193 \end{filecontents} |
|
194 \begin{document} |
|
195 |
|
196 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
197 \mode<presentation>{ |
|
198 \begin{frame}<1>[t] |
|
199 \frametitle{% |
|
200 \begin{tabular}{@ {}c@ {}} |
|
201 \\[-3mm] |
|
202 \LARGE Automata and \\[-2mm] |
|
203 \LARGE Formal Languages (6)\\[3mm] |
|
204 \end{tabular}} |
|
205 |
|
206 \normalsize |
|
207 \begin{center} |
|
208 \begin{tabular}{ll} |
|
209 Email: & christian.urban at kcl.ac.uk\\ |
|
210 Of$\!$fice: & S1.27 (1st floor Strand Building)\\ |
|
211 Slides: & KEATS (also home work is there)\\ |
|
212 \end{tabular} |
|
213 \end{center} |
|
214 |
|
215 |
|
216 \end{frame}} |
|
217 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
218 |
|
219 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
220 \mode<presentation>{ |
|
221 \begin{frame}[c] |
|
222 \frametitle{\begin{tabular}{c}ReDoS\end{tabular}} |
|
223 |
|
224 \begin{itemize} |
|
225 \item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice\bigskip |
|
226 \item ``Regular Expressions Will Stab You in the Back''\bigskip |
|
227 \item Evil regular expressions\medskip |
|
228 \begin{itemize} |
|
229 \item \bl{$(a?\{n\})a\{n\}$} |
|
230 \item \bl{$(a^+)^+$} |
|
231 \item \bl{$([a-zA-Z]^+)^*$} |
|
232 \item \bl{$(a + aa)^+$} |
|
233 \item \bl{$(a + a?)^+$} |
|
234 \end{itemize} |
|
235 \end{itemize} |
|
236 |
|
237 \end{frame}} |
|
238 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
239 |
|
240 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
241 \mode<presentation>{ |
|
242 \begin{frame}[c] |
|
243 \frametitle{\begin{tabular}{c}Regexp Matching\end{tabular}} |
|
244 |
|
245 Given a regular expression |
|
246 |
|
247 \begin{enumerate} |
|
248 \item you might convert it into a DFA (subset construction) |
|
249 \item you might try all possible paths in an NFA via backtracking |
|
250 \item you might try all paths in an NFA in parallel |
|
251 \item you might try to convert the DFA ``lazily'' |
|
252 \end{enumerate}\bigskip |
|
253 |
|
254 Often No~2 is implemented (sometimes there are even good reasons for doing this). |
|
255 |
|
256 \end{frame}} |
|
257 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
258 |
|
259 |
|
260 |
|
261 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
262 \mode<presentation>{ |
|
263 \begin{frame}[c] |
|
264 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\})a\{n\}$} in Python\end{tabular}} |
|
265 |
|
266 \begin{tikzpicture}[y=.2cm, x=.3cm] |
|
267 %axis |
|
268 \draw (0,0) -- coordinate (x axis mid) (30,0); |
|
269 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
270 %ticks |
|
271 \foreach \x in {0,5,...,30} |
|
272 \draw (\x,1pt) -- (\x,-3pt) |
|
273 node[anchor=north] {\x}; |
|
274 \foreach \y in {0,5,...,30} |
|
275 \draw (1pt,\y) -- (-3pt,\y) |
|
276 node[anchor=east] {\y}; |
|
277 %labels |
|
278 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
279 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
280 |
|
281 %plots |
|
282 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
283 file {re-python.data}; |
|
284 \only<2->{ |
|
285 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
286 file {re1.data};} |
|
287 \only<3->{ |
|
288 \draw[color=green] plot[mark=square*, mark options={fill=white} ] |
|
289 file {re2.data};} |
|
290 |
|
291 %legend |
|
292 \begin{scope}[shift={(4,20)}] |
|
293 \draw[color=blue] (0,0) -- |
|
294 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
295 node[right]{\small Python}; |
|
296 \only<2->{\draw[yshift=\baselineskip, color=red] (0,0) -- |
|
297 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
298 node[right]{\small Scala V1};} |
|
299 \only<3->{ |
|
300 \draw[yshift=2\baselineskip, color=green] (0,0) -- |
|
301 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
302 node[right]{\small Scala V2 with simplifications};} |
|
303 \end{scope} |
|
304 \end{tikzpicture} |
|
305 |
|
306 \end{frame}} |
|
307 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
308 |
|
309 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
310 \mode<presentation>{ |
|
311 \begin{frame}[c] |
|
312 |
|
313 |
|
314 \begin{tikzpicture}[y=.7cm, x=.0009cm] |
|
315 %axis |
|
316 \draw (0,0) -- coordinate (x axis mid) (10000,0); |
|
317 \draw (0,0) -- coordinate (y axis mid) (0,6); |
|
318 %ticks |
|
319 \foreach \x in {0,2000,...,10000} |
|
320 \draw (\x,1pt) -- (\x,-3pt) |
|
321 node[anchor=north] {\x}; |
|
322 \foreach \y in {0,1,...,6} |
|
323 \draw (1pt,\y) -- (-3pt,\y) |
|
324 node[anchor=east] {\y}; |
|
325 %labels |
|
326 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
327 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
328 |
|
329 %plots |
|
330 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
331 file {re-internal.data}; |
|
332 \only<2->{ |
|
333 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
334 file {re3.data};} |
|
335 |
|
336 %legend |
|
337 \begin{scope}[shift={(2000,4)}] |
|
338 \draw[color=blue] (0,0) -- |
|
339 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
340 node[right]{\small Scala Internal}; |
|
341 \only<2->{ |
|
342 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
343 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
344 node[right]{\small Scala V3 with explicit $\_\{\_\}$};} |
|
345 \end{scope} |
|
346 \end{tikzpicture} |
|
347 |
|
348 \end{frame}} |
|
349 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
350 |
|
351 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
352 \mode<presentation>{ |
|
353 \begin{frame}[c] |
|
354 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
|
355 |
|
356 Last week I showed you\bigskip |
|
357 |
|
358 \begin{itemize} |
|
359 \item an algorithm for automata minimisation |
|
360 |
|
361 \item an algorithm for transforming a regular expression into an NFA |
|
362 |
|
363 \item an algorithm for transforming an NFA into a DFA (subset construction) |
|
364 |
|
365 \end{itemize} |
|
366 |
|
367 \end{frame}} |
|
368 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
369 |
|
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
371 \mode<presentation>{ |
|
372 \begin{frame}[c] |
|
373 \frametitle{\begin{tabular}{c}This Week\end{tabular}} |
|
374 |
|
375 Go over the algorithms again, but with two new things and \ldots\medskip |
|
376 |
|
377 \begin{itemize} |
|
378 \item with the example: what is the regular expression that accepts every string, except those ending |
|
379 in \bl{aa}?\medskip |
|
380 |
|
381 \item Go over the proof for \bl{$L(rev(r)) = Rev(L(r))$}.\medskip |
|
382 |
|
383 \item Anything else so far. |
|
384 \end{itemize} |
|
385 |
|
386 \end{frame}} |
|
387 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
388 |
|
389 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
390 \mode<presentation>{ |
|
391 \begin{frame}[c] |
|
392 \frametitle{\begin{tabular}{c}Proofs By Induction\end{tabular}} |
|
393 |
|
394 \begin{itemize} |
|
395 \item \bl{$P$} holds for \bl{$\varnothing$}, \bl{$\epsilon$} and \bl{c}\bigskip |
|
396 \item \bl{$P$} holds for \bl{r$_1$ + r$_2$} under the assumption that \bl{$P$} already |
|
397 holds for \bl{r$_1$} and \bl{r$_2$}.\bigskip |
|
398 \item \bl{$P$} holds for \bl{r$_1$ $\cdot$ r$_2$} under the assumption that \bl{$P$} already |
|
399 holds for \bl{r$_1$} and \bl{r$_2$}. |
|
400 \item \bl{$P$} holds for \bl{r$^*$} under the assumption that \bl{$P$} already |
|
401 holds for \bl{r}. |
|
402 \end{itemize} |
|
403 |
|
404 \begin{center} |
|
405 \bl{$P(r):\;\;L(rev(r)) = Rev(L(r))$} |
|
406 \end{center} |
|
407 |
|
408 \end{frame}} |
|
409 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
410 |
|
411 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
412 \mode<presentation>{ |
|
413 \begin{frame}[t] |
|
414 |
|
415 What is the regular expression that accepts every string, except those ending |
|
416 in \bl{aa}?\pause\bigskip |
|
417 |
|
418 \begin{center} |
|
419 \begin{tabular}{l} |
|
420 \bl{(a + b)$^*$ba}\\ |
|
421 \bl{(a + b)$^*$ab}\\ |
|
422 \bl{(a + b)$^*$bb}\\\pause |
|
423 \bl{a}\\ |
|
424 \bl{\texttt{""}} |
|
425 \end{tabular} |
|
426 \end{center}\pause |
|
427 |
|
428 What are the strings to be avoided?\pause\medskip |
|
429 |
|
430 \begin{center} |
|
431 \bl{(a + b)$^*$aa} |
|
432 \end{center} |
|
433 |
|
434 \end{frame}} |
|
435 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
436 |
|
437 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
438 \mode<presentation>{ |
|
439 \begin{frame}[t] |
|
440 |
|
441 An NFA for \bl{(a + b)$^*$aa} |
|
442 |
|
443 \begin{center} |
|
444 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
445 \node[state, initial] (q0) at ( 0,1) {$q_0$}; |
|
446 \node[state] (q1) at ( 1,1) {$q_1$}; |
|
447 \node[state, accepting] (q2) at ( 2,1) {$q_2$}; |
|
448 \path[->] (q0) edge node[above] {$a$} (q1) |
|
449 (q1) edge node[above] {$a$} (q2) |
|
450 (q0) edge [loop below] node {$a$} () |
|
451 (q0) edge [loop above] node {$b$} () |
|
452 ; |
|
453 \end{tikzpicture} |
|
454 \end{center}\pause |
|
455 |
|
456 Minimisation for DFAs\\ |
|
457 Subset Construction for NFAs |
|
458 |
|
459 \end{frame}} |
|
460 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
461 |
|
462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
463 \mode<presentation>{ |
|
464 \begin{frame}[c] |
|
465 \frametitle{\begin{tabular}{c}DFA Minimisation\end{tabular}} |
|
466 |
|
467 |
|
468 \begin{enumerate} |
|
469 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
470 \item Mark all pairs that accepting and non-accepting states |
|
471 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
472 \begin{center} |
|
473 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
474 \end{center} |
|
475 are marked. If yes, then also mark \bl{(q, p)}. |
|
476 \item Repeat last step until nothing changed. |
|
477 \item All unmarked pairs can be merged. |
|
478 \end{enumerate} |
|
479 |
|
480 \end{frame}} |
|
481 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
482 |
|
483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
484 \mode<presentation>{ |
|
485 \begin{frame}[c] |
|
486 |
|
487 Minimal DFA \only<1>{\bl{(a + b)$^*$aa}}\only<2->{\alert{not} \bl{(a + b)$^*$aa}} |
|
488 |
|
489 \begin{center} |
|
490 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
491 \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
492 \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};} |
|
493 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
494 \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
|
495 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
|
496 \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
497 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
498 (q1) edge[bend left] node[above] {$b$} (q0) |
|
499 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
500 (q1) edge node[above] {$a$} (q2) |
|
501 (q2) edge [loop right] node {$a$} () |
|
502 (q0) edge [loop below] node {$b$} () |
|
503 ; |
|
504 \end{tikzpicture} |
|
505 \end{center} |
|
506 |
|
507 \onslide<3>{How to get from a DFA to a regular expression?} |
|
508 |
|
509 \end{frame}} |
|
510 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
511 |
|
512 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
513 \mode<presentation>{ |
|
514 \begin{frame}[c] |
|
515 |
|
516 \begin{center} |
|
517 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
518 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
519 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
520 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
521 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
522 (q1) edge[bend left] node[above] {$b$} (q0) |
|
523 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
524 (q1) edge node[above] {$a$} (q2) |
|
525 (q2) edge [loop right] node {$a$} () |
|
526 (q0) edge [loop below] node {$b$} () |
|
527 ; |
|
528 \end{tikzpicture} |
|
529 \end{center}\pause\bigskip |
|
530 |
|
531 \onslide<2->{ |
|
532 \begin{center} |
|
533 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
534 \bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ |
|
535 \bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\ |
|
536 \bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\ |
|
537 |
|
538 \end{tabular} |
|
539 \end{center} |
|
540 } |
|
541 |
|
542 \end{frame}} |
|
543 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
544 |
|
545 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
546 \mode<presentation>{ |
|
547 \begin{frame}[c] |
|
548 |
|
549 \begin{center} |
|
550 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
551 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
552 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
553 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
554 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
555 (q1) edge[bend left] node[above] {$b$} (q0) |
|
556 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
557 (q1) edge node[above] {$a$} (q2) |
|
558 (q2) edge [loop right] node {$a$} () |
|
559 (q0) edge [loop below] node {$b$} () |
|
560 ; |
|
561 \end{tikzpicture} |
|
562 \end{center}\bigskip |
|
563 |
|
564 \onslide<2->{ |
|
565 \begin{center} |
|
566 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
567 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ |
|
568 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
|
569 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
|
570 |
|
571 \end{tabular} |
|
572 \end{center} |
|
573 } |
|
574 |
|
575 \onslide<3->{ |
|
576 Arden's Lemma: |
|
577 \begin{center} |
|
578 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
579 \end{center} |
|
580 } |
|
581 |
|
582 \end{frame}} |
|
583 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
584 |
|
585 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
586 \mode<presentation>{ |
|
587 \begin{frame}[c] |
|
588 \frametitle{\begin{tabular}{c}Algorithms on Automata\end{tabular}} |
|
589 |
|
590 |
|
591 \begin{itemize} |
|
592 \item Reg $\rightarrow$ NFA: Thompson-McNaughton-Yamada method\medskip |
|
593 \item NFA $\rightarrow$ DFA: Subset Construction\medskip |
|
594 \item DFA $\rightarrow$ Reg: Brzozowski's Algebraic Method\medskip |
|
595 \item DFA minimisation: Hopcrofts Algorithm\medskip |
|
596 \item complement DFA |
|
597 \end{itemize} |
|
598 |
|
599 \end{frame}} |
|
600 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
601 \newcommand{\qq}{\mbox{\texttt{"}}} |
|
602 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
603 \mode<presentation>{ |
|
604 \begin{frame}[c] |
|
605 \frametitle{\begin{tabular}{c}Grammars\end{tabular}} |
|
606 |
|
607 \begin{center} |
|
608 \bl{\begin{tabular}{lcl} |
|
609 $E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ |
|
610 $F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ |
|
611 $T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ |
|
612 \end{tabular}} |
|
613 \end{center} |
|
614 |
|
615 \bl{$E$}, \bl{$F$} and \bl{$T$} are non-terminals\\ |
|
616 \bl{$E$} is start symbol\\ |
|
617 \bl{$num$}, \bl{(}, \bl{)}, \bl{+} \ldots are terminals\bigskip\\ |
|
618 |
|
619 |
|
620 \bl{\texttt{(2*3)+(3+4)}} |
|
621 |
|
622 \end{frame}} |
|
623 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
624 |
|
625 |
|
626 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
627 \mode<presentation>{ |
|
628 \begin{frame}[c] |
|
629 |
|
630 \begin{center} |
|
631 \bl{\begin{tabular}{lcl} |
|
632 $E$ & $\rightarrow$ & $F + (F \cdot \qq*\qq \cdot F) + (F \cdot \qq\backslash\qq \cdot F)$\\ |
|
633 $F$ & $\rightarrow$ & $T + (T \cdot \qq\texttt{+}\qq \cdot T) + (T \cdot \qq\texttt{-}\qq \cdot T)$\\ |
|
634 $T$ & $\rightarrow$ & $num + (\qq\texttt{(}\qq \cdot E \cdot \qq\texttt{)}\qq)$\\ |
|
635 \end{tabular}} |
|
636 \end{center} |
|
637 |
|
638 \begin{center} |
|
639 \begin{tikzpicture}[level distance=8mm, blue] |
|
640 \node {E} |
|
641 child {node {F} |
|
642 child {node {T} |
|
643 child {node {\qq(\qq\,E\,\qq)\qq} |
|
644 child {node{F \qq*\qq{} F} |
|
645 child {node {T} child {node {2}}} |
|
646 child {node {T} child {node {3}}} |
|
647 } |
|
648 } |
|
649 } |
|
650 child {node {\qq+\qq}} |
|
651 child {node {T} |
|
652 child {node {\qq(\qq\,E\,\qq)\qq} |
|
653 child {node {F} |
|
654 child {node {T \qq+\qq{} T} |
|
655 child {node {3}} |
|
656 child {node {4}} |
|
657 } |
|
658 }} |
|
659 }}; |
|
660 \end{tikzpicture} |
|
661 \end{center} |
|
662 |
|
663 \begin{textblock}{5}(1, 5) |
|
664 \bl{\texttt{(2*3)+(3+4)}} |
|
665 \end{textblock} |
|
666 |
|
667 \end{frame}} |
|
668 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
669 |
|
670 \end{document} |
|
671 |
|
672 %%% Local Variables: |
|
673 %%% mode: latex |
|
674 %%% TeX-master: t |
|
675 %%% End: |
|
676 |