120 \end{center} |
229 \end{center} |
121 |
230 |
122 \end{frame}} |
231 \end{frame}} |
123 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
232 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
124 |
233 |
|
234 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
235 \mode<presentation>{ |
|
236 \begin{frame}[c] |
|
237 \frametitle{\begin{tabular}{c}DFAs\end{tabular}} |
|
238 |
|
239 A deterministic finite automaton consists of: |
|
240 |
|
241 \begin{itemize} |
|
242 \item a finite set of states, \bl{$Q$} |
|
243 \item one of these states is the start state, \bl{$q_0$} |
|
244 \item there is transition function, \bl{$\delta$}, and |
|
245 \item some states are accepting states, \bl{$F$} |
|
246 \medskip |
|
247 \end{itemize} |
|
248 |
|
249 \begin{center} |
|
250 \bl{$A(Q, q_0, \delta, F)$} |
|
251 \end{center} |
|
252 \end{frame}} |
|
253 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
254 |
|
255 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
256 \mode<presentation>{ |
|
257 \begin{frame}[c] |
|
258 \frametitle{\begin{tabular}{c}State Nodes\end{tabular}} |
|
259 |
|
260 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont |
|
261 \lstinputlisting{../progs/appA.scala}}} |
|
262 |
|
263 \end{frame}} |
|
264 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
265 |
|
266 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
267 \mode<presentation>{ |
|
268 \begin{frame}[c] |
|
269 \frametitle{\begin{tabular}{c}DFAs\;\;\;\end{tabular}} |
|
270 |
|
271 \mbox{}\\[7mm] |
|
272 |
|
273 \mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont |
|
274 \lstinputlisting{../progs/appB.scala}}} |
|
275 |
|
276 \only<2->{ |
|
277 \begin{textblock}{9}(7.5,0.5) |
|
278 \begin{tikzpicture} |
|
279 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] |
|
280 {\normalsize\color{darkgray} |
|
281 \begin{minipage}{6cm} |
|
282 \begin{tabular}{l} |
|
283 \bl{$\hat{\delta}(q, \texttt{""}) \dn q$}\\ |
|
284 \bl{$\hat{\delta}(q, c::s) \dn \hat{\delta}(\delta(q, c), s)$}\\[4mm] |
|
285 \bl{$\hat{\delta}(q_0, s) \in F$} |
|
286 \end{tabular} |
|
287 \end{minipage}}; |
|
288 \end{tikzpicture} |
|
289 \end{textblock}} |
|
290 |
|
291 \end{frame}} |
|
292 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
293 |
|
294 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
295 \mode<presentation>{ |
|
296 \begin{frame}[t] |
|
297 |
|
298 \mbox{}\hspace{-10mm} |
|
299 \begin{tikzpicture}[scale=0.6,>=stealth',very thick,auto, |
|
300 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
301 \node[state,initial] (q_0) {$q_0$}; |
|
302 \node[state] (q_1) [right=of q_0] {$q_1$}; |
|
303 \node[state] (q_2) [below right=of q_0] {$q_2$}; |
|
304 \node[state] (q_3) [right=of q_2] {$q_3$}; |
|
305 \node[state, accepting] (q_4) [right=of q_1] {$q_4$}; |
|
306 \path[->] (q_0) edge node [above] {\alert{$a$}} (q_1); |
|
307 \path[->] (q_1) edge node [above] {\alert{$a$}} (q_4); |
|
308 \path[->] (q_4) edge [loop right] node {\alert{$a, b$}} (); |
|
309 \path[->] (q_3) edge node [right] {\alert{$a$}} (q_4); |
|
310 \path[->] (q_2) edge node [above] {\alert{$a$}} (q_3); |
|
311 \path[->] (q_1) edge node [right] {\alert{$b$}} (q_2); |
|
312 \path[->] (q_0) edge node [above] {\alert{$b$}} (q_2); |
|
313 \path[->] (q_2) edge [loop left] node {\alert{$b$}} (); |
|
314 \path[->] (q_3) edge [bend left=95, looseness=1.3] node [below] {\alert{$b$}} (q_0); |
|
315 \end{tikzpicture} |
|
316 |
|
317 \only<1->{ |
|
318 \begin{textblock}{9}(7.4,3.5) |
|
319 \begin{tikzpicture} |
|
320 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] |
|
321 {\normalsize\color{darkgray} |
|
322 \begin{minipage}{6.6cm} |
|
323 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont |
|
324 \lstinputlisting{../progs/appC.scala}}} |
|
325 \end{minipage}}; |
|
326 \end{tikzpicture} |
|
327 \end{textblock}} |
|
328 |
|
329 \end{frame}} |
|
330 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
331 |
|
332 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
333 \mode<presentation>{ |
|
334 \begin{frame}[c] |
|
335 \frametitle{\begin{tabular}{c}NFAs\end{tabular}} |
|
336 |
|
337 A non-deterministic finite automaton \bl{$A(Q, q_0, \delta, F)$} consists of:\medskip |
|
338 |
|
339 \begin{itemize} |
|
340 \item a finite set of states, \bl{$Q$} |
|
341 \item one of these states is the start state, \bl{$q_0$} |
|
342 \item some states are accepting states, \bl{$F$}, |
|
343 \item there is transition \alert{relation}, \bl{$\delta$}, and |
|
344 \item there are \alert{silent} transitions\medskip |
|
345 \end{itemize} |
|
346 |
|
347 |
|
348 \begin{center} |
|
349 \begin{tabular}{c} |
|
350 \bl{$(q_1, a) \rightarrow q_2$}\\ |
|
351 \bl{$(q_1, a) \rightarrow q_3$}\\ |
|
352 \end{tabular} |
|
353 \hspace{10mm} |
|
354 \begin{tabular}{c} |
|
355 \bl{$(q_1, \epsilon) \rightarrow q_2$}\\ |
|
356 \end{tabular} |
|
357 \end{center} |
|
358 |
|
359 \end{frame}} |
|
360 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
361 |
|
362 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
363 \mode<presentation>{ |
|
364 \begin{frame}[c] |
|
365 |
|
366 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont |
|
367 \lstinputlisting{../progs/appD.scala}}} |
|
368 |
|
369 \end{frame}} |
|
370 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
371 |
|
372 |
|
373 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
374 \mode<presentation>{ |
|
375 \begin{frame}[t] |
|
376 |
|
377 \mbox{}\hspace{-10mm} |
|
378 \begin{tikzpicture}[scale=0.6,>=stealth',very thick,auto, |
|
379 every state/.style={minimum size=0pt,inner sep=2pt,draw=blue!50,very thick,fill=blue!20},] |
|
380 \node[state,initial] (q_0) {$q_0$}; |
|
381 \node[state] (q_1) [above=of q_0] {$q_1$}; |
|
382 \node[state, accepting] (q_2) [below=of q_0] {$q_2$}; |
|
383 \path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_1); |
|
384 \path[->] (q_0) edge node [left] {\alert{$\epsilon$}} (q_2); |
|
385 \path[->] (q_0) edge [loop right] node {\alert{$a$}} (); |
|
386 \path[->] (q_1) edge [loop above] node {\alert{$a$}} (); |
|
387 \path[->] (q_2) edge [loop below] node {\alert{$b$}} (); |
|
388 \end{tikzpicture} |
|
389 |
|
390 \only<1->{ |
|
391 \begin{textblock}{9}(6,1.5) |
|
392 \begin{tikzpicture} |
|
393 \draw (0,0) node[inner sep=2mm,fill=cream, ultra thick, draw=red, rounded corners=2mm] |
|
394 {\normalsize\color{darkgray} |
|
395 \begin{minipage}{7cm} |
|
396 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{8}{10}\selectfont |
|
397 \lstinputlisting{../progs/appE.scala}}} |
|
398 \end{minipage}}; |
|
399 \end{tikzpicture} |
|
400 \end{textblock}} |
|
401 |
|
402 \end{frame}} |
|
403 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
404 |
|
405 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
406 \mode<presentation>{ |
|
407 \begin{frame}[c] |
|
408 \frametitle{Rexp to NFA} |
|
409 |
|
410 Thompson's construction of a NFA from a regular expression: |
|
411 |
|
412 \begin{center} |
|
413 \begin{tabular}[t]{l@{\hspace{10mm}}l} |
|
414 \raisebox{1mm}{\bl{$\varnothing$}} & |
|
415 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
|
416 \node[state, initial] (q_0) {$\mbox{}$}; |
|
417 \end{tikzpicture}\\\\ |
|
418 \raisebox{1mm}{\bl{$\epsilon$}} & |
|
419 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
|
420 \node[state, initial, accepting] (q_0) {$\mbox{}$}; |
|
421 \end{tikzpicture}\\\\ |
|
422 \raisebox{2mm}{\bl{$c$}} & |
|
423 \begin{tikzpicture}[scale=0.7,>=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
|
424 \node[state, initial] (q_0) {$\mbox{}$}; |
|
425 \node[state, accepting] (q_1) [right=of q_0] {$\mbox{}$}; |
|
426 \path[->] (q_0) edge node [below] {\alert{$c$}} (q_1); |
|
427 \end{tikzpicture}\\\\ |
|
428 \end{tabular} |
|
429 \end{center} |
|
430 |
|
431 \end{frame}} |
|
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
433 |
|
434 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
435 \mode<presentation>{ |
|
436 \begin{frame}[t] |
|
437 \frametitle{Case $r_1\cdot r_2$} |
|
438 |
|
439 \mbox{}\bigskip |
|
440 \onslide<1>{By recursion we are given two automata:\bigskip} |
|
441 |
|
442 {\centering\begin{tikzpicture}[node distance=3mm, |
|
443 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
|
444 \node[state, initial] (q_0) {$\mbox{}$}; |
|
445 \node (r_1) [right=of q_0] {$\ldots$}; |
|
446 \only<1>{ |
|
447 \node[state, accepting] (t_1) [right=of r_1] {$\mbox{}$}; |
|
448 \node[state, accepting] (t_2) [above=of t_1] {$\mbox{}$}; |
|
449 \node[state, accepting] (t_3) [below=of t_1] {$\mbox{}$};} |
|
450 \only<2>{ |
|
451 \node[state] (t_1) [right=of r_1] {$\mbox{}$}; |
|
452 \node[state] (t_2) [above=of t_1] {$\mbox{}$}; |
|
453 \node[state] (t_3) [below=of t_1] {$\mbox{}$};} |
|
454 \only<1>{\node[state, initial] (a_0) [right=2.5cm of t_1] {$\mbox{}$};} |
|
455 \only<2>{\node[state] (a_0) [right=2.5cm of t_1] {$\mbox{}$};} |
|
456 \node (b_1) [right=of a_0] {$\ldots$}; |
|
457 \node[state, accepting] (c_1) [right=of b_1] {$\mbox{}$}; |
|
458 \node[state, accepting] (c_2) [above=of c_1] {$\mbox{}$}; |
|
459 \node[state, accepting] (c_3) [below=of c_1] {$\mbox{}$}; |
|
460 \only<2>{ |
|
461 \path[->] (t_1) edge node [above, pos=0.3] {\alert{$\epsilon$}} (a_0); |
|
462 \path[->] (t_2) edge node [above] {\alert{$\epsilon$}} (a_0); |
|
463 \path[->] (t_3) edge node [below] {\alert{$\epsilon$}} (a_0); |
|
464 } |
|
465 \begin{pgfonlayer}{background} |
|
466 \only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (r_1) (t_1) (t_2) (t_3)] {};} |
|
467 \only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (a_0) (b_1) (c_1) (c_2) (c_3)] {};} |
|
468 \only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (q_0) (c_1) (c_2) (c_3)] {};} |
|
469 \only<1>{\node [yshift=2mm] at (1.north) {\bl{$r_1$}};} |
|
470 \only<1>{\node [yshift=2mm] at (2.north) {\bl{$r_2$}};} |
|
471 \only<2>{\node [yshift=2mm] at (3.north) {\bl{$r_1\cdot r_2$}};} |
|
472 \end{pgfonlayer} |
|
473 \end{tikzpicture}}\bigskip\bigskip |
|
474 |
|
475 \small |
|
476 We need to (1) change the accepting nodes of the first automaton into non-accepting nodes, and (2) connect them |
|
477 via $\epsilon$-transitions to the starting state of the second automaton. |
|
478 |
|
479 \end{frame}} |
|
480 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
481 |
|
482 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
483 \mode<presentation>{ |
|
484 \begin{frame}[t] |
|
485 \frametitle{Case $r_1+ r_2$} |
|
486 |
|
487 \onslide<1>{By recursion we are given two automata:\smallskip} |
|
488 |
|
489 \hspace{2cm}\begin{tikzpicture}[node distance=3mm, |
|
490 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
|
491 \onslide<1>{\node at (0,0) (1) {$\mbox{}$};} |
|
492 \onslide<2>{\node at (0,0) [state, initial] (1) {$\mbox{}$};} |
|
493 \only<1>{ |
|
494 \node[state, initial] (2) [above right=16mm of 1] {$\mbox{}$}; |
|
495 \node[state, initial] (3) [below right=16mm of 1] {$\mbox{}$};} |
|
496 \only<2>{ |
|
497 \node[state] (2) [above right=16mm of 1] {$\mbox{}$}; |
|
498 \node[state] (3) [below right=16mm of 1] {$\mbox{}$};} |
|
499 |
|
500 \node (a) [right=of 2] {$\ldots$}; |
|
501 \node[state, accepting] (a1) [right=of a] {$\mbox{}$}; |
|
502 \node[state, accepting] (a2) [above=of a1] {$\mbox{}$}; |
|
503 \node[state, accepting] (a3) [below=of a1] {$\mbox{}$}; |
|
504 |
|
505 \node (b) [right=of 3] {$\ldots$}; |
|
506 \node[state, accepting] (b1) [right=of b] {$\mbox{}$}; |
|
507 \node[state, accepting] (b2) [above=of b1] {$\mbox{}$}; |
|
508 \node[state, accepting] (b3) [below=of b1] {$\mbox{}$}; |
|
509 \only<2>{ |
|
510 \path[->] (1) edge node [above] {\alert{$\epsilon$}} (2); |
|
511 \path[->] (1) edge node [below] {\alert{$\epsilon$}} (3); |
|
512 } |
|
513 \begin{pgfonlayer}{background} |
|
514 \only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};} |
|
515 \only<1>{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (3) (b1) (b2) (b3)] {};} |
|
516 \only<2>{\node (3) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3) (b2) (b3)] {};} |
|
517 \only<1>{\node [yshift=3mm] at (1.north) {\bl{$r_1$}};} |
|
518 \only<1>{\node [yshift=3mm] at (2.north) {\bl{$r_2$}};} |
|
519 \only<2>{\node [yshift=3mm] at (3.north) {\bl{$r_1+ r_2$}};} |
|
520 \end{pgfonlayer} |
|
521 \end{tikzpicture} |
|
522 |
|
523 \small |
|
524 We (1) need to introduce a new starting state and (2) connect it to the original two starting states. |
|
525 \end{frame}} |
|
526 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
527 |
|
528 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
529 \mode<presentation>{ |
|
530 \begin{frame}[c] |
|
531 \frametitle{Case $r^*$} |
|
532 |
|
533 \onslide<1>{By recursion we are given an automaton for $r$:\smallskip} |
|
534 |
|
535 \hspace{2cm}\begin{tikzpicture}[node distance=3mm, |
|
536 >=stealth',very thick, every state/.style={minimum size=3pt,draw=blue!50,very thick,fill=blue!20},] |
|
537 \onslide<1>{\node at (0,0) (1) {$\mbox{}$};} |
|
538 \onslide<2->{\node at (0,0) [state, initial,accepting] (1) {$\mbox{}$};} |
|
539 \only<1>{\node[state, initial] (2) [right=16mm of 1] {$\mbox{}$};} |
|
540 \only<2->{\node[state] (2) [right=16mm of 1] {$\mbox{}$};} |
|
541 \node (a) [right=of 2] {$\ldots$}; |
|
542 \only<1>{ |
|
543 \node[state, accepting] (a1) [right=of a] {$\mbox{}$}; |
|
544 \node[state, accepting] (a2) [above=of a1] {$\mbox{}$}; |
|
545 \node[state, accepting] (a3) [below=of a1] {$\mbox{}$};} |
|
546 \only<2->{ |
|
547 \node[state] (a1) [right=of a] {$\mbox{}$}; |
|
548 \node[state] (a2) [above=of a1] {$\mbox{}$}; |
|
549 \node[state] (a3) [below=of a1] {$\mbox{}$};} |
|
550 \only<2->{ |
|
551 \path[->] (1) edge node [above] {\alert{$\epsilon$}} (2); |
|
552 \path[->] (a1) edge [bend left=45] node [above] {\alert{$\epsilon$}} (1); |
|
553 \path[->] (a2) edge [bend right] node [below] {\alert{$\epsilon$}} (1); |
|
554 \path[->] (a3) edge [bend left=45] node [below] {\alert{$\epsilon$}} (1); |
|
555 |
|
556 } |
|
557 \begin{pgfonlayer}{background} |
|
558 \only<1>{\node (1) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (2) (a1) (a2) (a3)] {};} |
|
559 \only<2->{\node (2) [rounded corners, inner sep=1mm, thick, draw=black!60, fill=black!20, fit= (1) (a2) (a3)] {};} |
|
560 \only<1>{\node [yshift=3mm] at (1.north) {\bl{$r$}};} |
|
561 \only<2->{\node [yshift=3mm] at (2.north) {\bl{$r^*$}};} |
|
562 \end{pgfonlayer} |
|
563 \end{tikzpicture}\bigskip |
|
564 |
|
565 \onslide<3->{ |
|
566 Why can't we just have an epsilon transition from the accepting states to the starting state?} |
|
567 |
|
568 \end{frame}} |
|
569 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
570 |
|
571 |
|
572 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
573 \mode<presentation>{ |
|
574 \begin{frame}[t] |
|
575 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
576 |
|
577 \mbox{}\\[-13mm] |
|
578 |
|
579 \begin{tikzpicture}[y=.2cm, x=.09cm] |
|
580 %axis |
|
581 \draw (0,0) -- coordinate (x axis mid) (100,0); |
|
582 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
583 %ticks |
|
584 \foreach \x in {0,10,...,100} |
|
585 \draw (\x,1pt) -- (\x,-3pt) |
|
586 node[anchor=north] {\x}; |
|
587 \foreach \y in {0,5,...,30} |
|
588 \draw (1pt,\y) -- (-3pt,\y) |
|
589 node[anchor=east] {\y}; |
|
590 %labels |
|
591 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
592 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
593 |
|
594 %plots |
|
595 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
596 file {re-python.data}; |
|
597 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
598 file {nfa.data}; |
|
599 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
600 file {re-ruby.data}; |
|
601 |
|
602 |
|
603 %legend |
|
604 \begin{scope}[shift={(4,20)}] |
|
605 \draw[color=blue] (0,0) -- |
|
606 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
607 node[right]{\small Python}; |
|
608 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
609 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
610 node[right]{\small Ruby}; |
|
611 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
612 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
613 node[right]{\small NFA 1}; |
|
614 \end{scope} |
|
615 \end{tikzpicture} |
|
616 |
|
617 \end{frame}} |
|
618 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
619 |
|
620 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
621 \mode<presentation>{ |
|
622 \begin{frame}[c] |
|
623 \frametitle{Greedy Depth-First} |
|
624 |
|
625 \hspace{5mm}\mbox{{\lstset{language=Scala}\consolas\fontsize{9}{10}\selectfont |
|
626 \lstinputlisting{../progs/appG.scala}}} |
|
627 |
|
628 \end{frame}} |
|
629 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
630 |
|
631 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
632 \mode<presentation>{ |
|
633 \begin{frame}[t] |
|
634 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
635 |
|
636 \mbox{}\\[-13mm] |
|
637 |
|
638 \begin{tikzpicture}[y=.2cm, x=.3cm] |
|
639 %axis |
|
640 \draw (0,0) -- coordinate (x axis mid) (30,0); |
|
641 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
642 %ticks |
|
643 \foreach \x in {0,5,...,30} |
|
644 \draw (\x,1pt) -- (\x,-3pt) |
|
645 node[anchor=north] {\x}; |
|
646 \foreach \y in {0,5,...,30} |
|
647 \draw (1pt,\y) -- (-3pt,\y) |
|
648 node[anchor=east] {\y}; |
|
649 %labels |
|
650 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
651 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
652 |
|
653 %plots |
|
654 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
655 file {re-python.data}; |
|
656 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
657 file {nfasearch.data}; |
|
658 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
659 file {re-ruby.data}; |
|
660 |
|
661 %legend |
|
662 \begin{scope}[shift={(4,20)}] |
|
663 \draw[color=blue] (0,0) -- |
|
664 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
665 node[right]{\small Python}; |
|
666 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
667 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
668 node[right]{\small Ruby}; |
|
669 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
670 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
671 node[right]{\small NFA 2}; |
|
672 \end{scope} |
|
673 \end{tikzpicture} |
|
674 |
|
675 \end{frame}} |
|
676 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
677 |
|
678 |
|
679 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
680 \mode<presentation>{ |
|
681 \begin{frame}<2>[c] |
|
682 \frametitle{DFA to Rexp} |
|
683 |
|
684 \begin{center} |
|
685 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
686 \only<1>{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
687 \only<2->{\node[state, initial,accepting] (q0) at ( 0,1) {$q_0$};} |
|
688 \only<1>{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
689 \only<2->{\node[state,accepting] (q1) at ( 1,1) {$q_1$};} |
|
690 \only<1>{\node[state, accepting] (q2) at ( 2,1) {$q_2$};} |
|
691 \only<2->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
692 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
693 (q1) edge[bend left] node[above] {$b$} (q0) |
|
694 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
695 (q1) edge node[above] {$a$} (q2) |
|
696 (q2) edge [loop right] node {$a$} () |
|
697 (q0) edge [loop below] node {$b$} () |
|
698 ; |
|
699 \end{tikzpicture} |
|
700 \end{center} |
|
701 |
|
702 \onslide<3>{How to get from a DFA to a regular expression?} |
|
703 |
|
704 \end{frame}} |
|
705 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
706 |
|
707 |
|
708 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
709 \mode<presentation>{ |
|
710 \begin{frame}[c] |
|
711 |
|
712 \begin{center} |
|
713 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
714 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
715 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
716 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
717 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
718 (q1) edge[bend left] node[above] {$b$} (q0) |
|
719 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
720 (q1) edge node[above] {$a$} (q2) |
|
721 (q2) edge [loop right] node {$a$} () |
|
722 (q0) edge [loop below] node {$b$} () |
|
723 ; |
|
724 \end{tikzpicture} |
|
725 \end{center}\pause\bigskip |
|
726 |
|
727 \onslide<2->{ |
|
728 \begin{center} |
|
729 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
730 \bl{$q_0$} & \bl{$=$} & \bl{$2\, q_0 + 3 \,q_1 + 4\, q_2$}\\ |
|
731 \bl{$q_1$} & \bl{$=$} & \bl{$2 \,q_0 + 3\, q_1 + 1\, q_2$}\\ |
|
732 \bl{$q_2$} & \bl{$=$} & \bl{$1\, q_0 + 5\, q_1 + 2\, q_2$}\\ |
|
733 |
|
734 \end{tabular} |
|
735 \end{center} |
|
736 } |
|
737 |
|
738 \end{frame}} |
|
739 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
740 |
|
741 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
742 \mode<presentation>{ |
|
743 \begin{frame}[c] |
|
744 |
|
745 \begin{center} |
|
746 \begin{tikzpicture}[scale=2, line width=0.5mm] |
|
747 \only<1->{\node[state, initial] (q0) at ( 0,1) {$q_0$};} |
|
748 \only<1->{\node[state] (q1) at ( 1,1) {$q_1$};} |
|
749 \only<1->{\node[state] (q2) at ( 2,1) {$q_2$};} |
|
750 \path[->] (q0) edge[bend left] node[above] {$a$} (q1) |
|
751 (q1) edge[bend left] node[above] {$b$} (q0) |
|
752 (q2) edge[bend left=50] node[below] {$b$} (q0) |
|
753 (q1) edge node[above] {$a$} (q2) |
|
754 (q2) edge [loop right] node {$a$} () |
|
755 (q0) edge [loop below] node {$b$} () |
|
756 ; |
|
757 \end{tikzpicture} |
|
758 \end{center}\bigskip |
|
759 |
|
760 \onslide<2->{ |
|
761 \begin{center} |
|
762 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l} |
|
763 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$}\\ |
|
764 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
|
765 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
|
766 |
|
767 \end{tabular} |
|
768 \end{center} |
|
769 } |
|
770 |
|
771 \onslide<3->{ |
|
772 Arden's Lemma: |
|
773 \begin{center} |
|
774 If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$} |
|
775 \end{center} |
|
776 } |
|
777 |
|
778 \end{frame}} |
|
779 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
780 |
|
781 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
782 \mode<presentation>{ |
|
783 \begin{frame}[c] |
|
784 \frametitle{DFA Minimisation} |
|
785 |
|
786 \begin{enumerate} |
|
787 \item Take all pairs \bl{$(q, p)$} with \bl{$q \not= p$} |
|
788 \item Mark all pairs that accepting and non-accepting states |
|
789 \item For all unmarked pairs \bl{$(q, p)$} and all characters \bl{$c$} tests wether |
|
790 \begin{center} |
|
791 \bl{$(\delta(q, c), \delta(p,c))$} |
|
792 \end{center} |
|
793 are marked. If yes, then also mark \bl{$(q, p)$}. |
|
794 \item Repeat last step until no chance. |
|
795 \item All unmarked pairs can be merged. |
|
796 \end{enumerate} |
|
797 |
|
798 \end{frame}} |
|
799 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
125 |
800 |
126 |
801 |
127 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
802 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
128 \mode<presentation>{ |
803 \mode<presentation>{ |
129 \begin{frame}<1-2>[c] |
804 \begin{frame}<1-2>[c] |
166 \end{center} |
841 \end{center} |
167 |
842 |
168 \end{frame}} |
843 \end{frame}} |
169 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
844 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
170 |
845 |
171 |
846 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
172 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
847 \mode<presentation>{ |
173 \mode<presentation>{ |
848 \begin{frame}[c] |
174 \begin{frame}[c] |
|
175 |
|
176 \begin{enumerate} |
|
177 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
178 \item Mark all pairs that are accepting and non-accepting states |
|
179 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
180 \begin{center} |
|
181 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
182 \end{center} |
|
183 are marked. If yes, then also mark \bl{(q, p)} |
|
184 \item Repeat last step until no chance. |
|
185 \item All unmarked pairs can be merged. |
|
186 \end{enumerate} |
|
187 |
|
188 \end{frame}} |
|
189 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
190 |
|
191 |
|
192 |
|
193 |
|
194 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
195 \mode<presentation>{ |
|
196 \begin{frame}[c] |
|
197 \frametitle{\begin{tabular}{c}Last Week\end{tabular}} |
|
198 |
|
199 Last week I showed you\bigskip |
|
200 |
849 |
201 \begin{itemize} |
850 \begin{itemize} |
202 \item a tokenizer taking a list of regular expressions\bigskip |
851 \item Assuming you have the alphabet \bl{$\{a, b, c\}$}\bigskip |
203 |
852 \item Give a regular expression that can recognise all strings that have at least one \bl{$b$}. |
204 \item tokenization identifies lexeme in an input stream of characters (or string) |
|
205 and cathegorizes them into tokens |
|
206 |
|
207 \end{itemize} |
853 \end{itemize} |
208 |
854 |
209 \end{frame}} |
855 \end{frame}} |
210 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
856 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
211 |
|
212 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
213 \mode<presentation>{ |
|
214 \begin{frame}[c] |
|
215 \frametitle{\begin{tabular}{c}Two Rules\end{tabular}} |
|
216 |
|
217 \begin{itemize} |
|
218 \item Longest match rule (maximal munch rule): The |
|
219 longest initial substring matched by any regular expression is taken |
|
220 as next token.\bigskip |
|
221 |
|
222 \item Rule priority: |
|
223 For a particular longest initial substring, the first regular |
|
224 expression that can match determines the token. |
|
225 |
|
226 \end{itemize} |
|
227 |
|
228 %\url{http://www.technologyreview.com/tr10/?year=2011} |
|
229 |
|
230 %finite deterministic automata/ nondeterministic automaton |
|
231 |
|
232 %\item problem with infix operations, for example i-12 |
|
233 |
|
234 |
|
235 \end{frame}} |
|
236 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
237 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
238 |
|
239 \mode<presentation>{ |
|
240 \begin{frame}[t] |
|
241 |
|
242 \begin{center} |
|
243 \texttt{"if true then then 42 else +"} |
|
244 \end{center} |
|
245 |
|
246 |
|
247 \begin{tabular}{@{}l} |
|
248 KEYWORD: \\ |
|
249 \hspace{5mm}\texttt{"if"}, \texttt{"then"}, \texttt{"else"},\\ |
|
250 WHITESPACE:\\ |
|
251 \hspace{5mm}\texttt{" "}, \texttt{"$\backslash$n"},\\ |
|
252 IDENT:\\ |
|
253 \hspace{5mm}LETTER $\cdot$ (LETTER + DIGIT + \texttt{"\_"})$^*$\\ |
|
254 NUM:\\ |
|
255 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\ |
|
256 OP:\\ |
|
257 \hspace{5mm}\texttt{"+"}\\ |
|
258 COMMENT:\\ |
|
259 \hspace{5mm}\texttt{"$\slash$*"} $\cdot$ (ALL$^*$ $\cdot$ \texttt{"*$\slash$"} $\cdot$ ALL$^*$) $\cdot$ \texttt{"*$\slash$"} |
|
260 \end{tabular} |
|
261 |
|
262 \end{frame}} |
|
263 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
264 |
|
265 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
266 \mode<presentation>{ |
|
267 \begin{frame}[t] |
|
268 |
|
269 \begin{center} |
|
270 \texttt{"if true then then 42 else +"} |
|
271 \end{center} |
|
272 |
|
273 \only<1>{ |
|
274 \small\begin{tabular}{l} |
|
275 KEYWORD(if),\\ |
|
276 WHITESPACE,\\ |
|
277 IDENT(true),\\ |
|
278 WHITESPACE,\\ |
|
279 KEYWORD(then),\\ |
|
280 WHITESPACE,\\ |
|
281 KEYWORD(then),\\ |
|
282 WHITESPACE,\\ |
|
283 NUM(42),\\ |
|
284 WHITESPACE,\\ |
|
285 KEYWORD(else),\\ |
|
286 WHITESPACE,\\ |
|
287 OP(+) |
|
288 \end{tabular}} |
|
289 |
|
290 \only<2>{ |
|
291 \small\begin{tabular}{l} |
|
292 KEYWORD(if),\\ |
|
293 IDENT(true),\\ |
|
294 KEYWORD(then),\\ |
|
295 KEYWORD(then),\\ |
|
296 NUM(42),\\ |
|
297 KEYWORD(else),\\ |
|
298 OP(+) |
|
299 \end{tabular}} |
|
300 |
|
301 \end{frame}} |
|
302 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
303 |
|
304 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
305 \mode<presentation>{ |
|
306 \begin{frame}[c] |
|
307 |
|
308 |
|
309 There is one small problem with the tokenizer. How should we |
|
310 tokenize: |
|
311 |
|
312 \begin{center} |
|
313 \texttt{"x - 3"} |
|
314 \end{center} |
|
315 |
|
316 \begin{tabular}{@{}l} |
|
317 OP:\\ |
|
318 \hspace{5mm}\texttt{"+"}, \texttt{"-"}\\ |
|
319 NUM:\\ |
|
320 \hspace{5mm}(NONZERODIGIT $\cdot$ DIGIT$^*$) + \texttt{"0"}\\ |
|
321 NUMBER:\\ |
|
322 \hspace{5mm}NUM + (\texttt{"-"} $\cdot$ NUM)\\ |
|
323 \end{tabular} |
|
324 |
|
325 |
|
326 \end{frame}} |
|
327 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
328 |
|
329 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
330 \mode<presentation>{ |
|
331 \begin{frame}[c] |
|
332 \frametitle{\begin{tabular}{c}Negation\end{tabular}} |
|
333 |
|
334 Assume you have an alphabet consisting of the letters \bl{a}, \bl{b} and \bl{c} only. |
|
335 Find a regular expression that matches all strings \emph{except} \bl{ab}, \bl{ac} and \bl{cba}. |
|
336 |
|
337 \end{frame}} |
|
338 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
339 |
|
340 |
|
341 |
|
342 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
343 \mode<presentation>{ |
|
344 \begin{frame}[c] |
|
345 \frametitle{\begin{tabular}{c}Deterministic Finite Automata\end{tabular}} |
|
346 |
|
347 A deterministic finite automaton consists of: |
|
348 |
|
349 \begin{itemize} |
|
350 \item a finite set of states |
|
351 \item one of these states is the start state |
|
352 \item some states are accepting states, and |
|
353 \item there is transition function\medskip |
|
354 |
|
355 \small |
|
356 which takes a state and a character as arguments and produces a new state\smallskip\\ |
|
357 this function might not always be defined everywhere |
|
358 \end{itemize} |
|
359 |
|
360 \begin{center} |
|
361 \bl{$A(Q, q_0, F, \delta)$} |
|
362 \end{center} |
|
363 \end{frame}} |
|
364 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
365 |
|
366 |
|
367 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
368 \mode<presentation>{ |
|
369 \begin{frame}[c] |
|
370 |
|
371 \begin{center} |
|
372 \includegraphics[scale=0.7]{pics/ch3.jpg} |
|
373 \end{center}\pause |
|
374 |
|
375 \begin{itemize} |
|
376 \item start can be an accepting state |
|
377 \item it is possible that there is no accepting state |
|
378 \item all states might be accepting (but does not necessarily mean all strings are accepted) |
|
379 \end{itemize} |
|
380 |
|
381 \end{frame}} |
|
382 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
383 |
|
384 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
385 \mode<presentation>{ |
|
386 \begin{frame}[c] |
|
387 |
|
388 \begin{center} |
|
389 \includegraphics[scale=0.7]{pics/ch3.jpg} |
|
390 \end{center} |
|
391 |
|
392 for this automaton \bl{$\delta$} is the function\\ |
|
393 |
|
394 \begin{center} |
|
395 \begin{tabular}{lll} |
|
396 \bl{(q$_0$, a) $\rightarrow$ q$_1$} & \bl{(q$_1$, a) $\rightarrow$ q$_4$} & \bl{(q$_4$, a) $\rightarrow$ q$_4$}\\ |
|
397 \bl{(q$_0$, b) $\rightarrow$ q$_2$} & \bl{(q$_1$, b) $\rightarrow$ q$_2$} & \bl{(q$_4$, b) $\rightarrow$ q$_4$}\\ |
|
398 \end{tabular}\ldots |
|
399 \end{center} |
|
400 |
|
401 \end{frame}} |
|
402 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
403 |
|
404 |
|
405 |
|
406 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
407 \mode<presentation>{ |
|
408 \begin{frame}[t] |
|
409 \frametitle{\begin{tabular}{c}Accepting a String\end{tabular}} |
|
410 |
|
411 Given |
|
412 |
|
413 \begin{center} |
|
414 \bl{$A(Q, q_0, F, \delta)$} |
|
415 \end{center} |
|
416 |
|
417 you can define |
|
418 |
|
419 \begin{center} |
|
420 \begin{tabular}{l} |
|
421 \bl{$\hat{\delta}(q, \texttt{""}) = q$}\\ |
|
422 \bl{$\hat{\delta}(q, c::s) = \hat{\delta}(\delta(q, c), s)$}\\ |
|
423 \end{tabular} |
|
424 \end{center}\pause |
|
425 |
|
426 Whether a string \bl{$s$} is accepted by \bl{$A$}? |
|
427 |
|
428 \begin{center} |
|
429 \hspace{5mm}\bl{$\hat{\delta}(q_0, s) \in F$} |
|
430 \end{center} |
|
431 \end{frame}} |
|
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
433 |
|
434 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
435 \mode<presentation>{ |
|
436 \begin{frame}[c] |
|
437 \frametitle{\begin{tabular}{c}Non-Deterministic\\[-1mm] Finite Automata\end{tabular}} |
|
438 |
|
439 A non-deterministic finite automaton consists again of: |
|
440 |
|
441 \begin{itemize} |
|
442 \item a finite set of states |
|
443 \item one of these states is the start state |
|
444 \item some states are accepting states, and |
|
445 \item there is transition \alert{relation}\medskip |
|
446 \end{itemize} |
|
447 |
|
448 |
|
449 \begin{center} |
|
450 \begin{tabular}{c} |
|
451 \bl{(q$_1$, a) $\rightarrow$ q$_2$}\\ |
|
452 \bl{(q$_1$, a) $\rightarrow$ q$_3$}\\ |
|
453 \end{tabular} |
|
454 \hspace{10mm} |
|
455 \begin{tabular}{c} |
|
456 \bl{(q$_1$, $\epsilon$) $\rightarrow$ q$_2$}\\ |
|
457 \end{tabular} |
|
458 \end{center} |
|
459 |
|
460 \end{frame}} |
|
461 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
462 |
|
463 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
464 \mode<presentation>{ |
|
465 \begin{frame}[c] |
|
466 |
|
467 \begin{center} |
|
468 \includegraphics[scale=0.7]{pics/ch5.jpg} |
|
469 \end{center} |
|
470 |
|
471 |
|
472 \end{frame}} |
|
473 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
474 |
|
475 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
476 \mode<presentation>{ |
|
477 \begin{frame}[c] |
|
478 |
|
479 \begin{center} |
|
480 \begin{tabular}[b]{ll} |
|
481 \bl{$\varnothing$} & \includegraphics[scale=0.7]{pics/NULL.jpg}\\\\ |
|
482 \bl{$\epsilon$} & \includegraphics[scale=0.7]{pics/epsilon.jpg}\\\\ |
|
483 \bl{c} & \includegraphics[scale=0.7]{pics/char.jpg}\\ |
|
484 \end{tabular} |
|
485 \end{center} |
|
486 |
|
487 \end{frame}} |
|
488 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
489 |
|
490 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
491 \mode<presentation>{ |
|
492 \begin{frame}[c] |
|
493 |
|
494 \begin{center} |
|
495 \begin{tabular}[t]{ll} |
|
496 \bl{r$_1$ $\cdot$ r$_2$} & \includegraphics[scale=0.6]{pics/seq.jpg}\\\\ |
|
497 \end{tabular} |
|
498 \end{center} |
|
499 |
|
500 \end{frame}} |
|
501 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
502 |
|
503 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
504 \mode<presentation>{ |
|
505 \begin{frame}[c] |
|
506 |
|
507 \begin{center} |
|
508 \begin{tabular}[t]{ll} |
|
509 \bl{r$_1$ + r$_2$} & \includegraphics[scale=0.7]{pics/alt.jpg}\\\\ |
|
510 \end{tabular} |
|
511 \end{center} |
|
512 |
|
513 \end{frame}} |
|
514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
515 |
|
516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
517 \mode<presentation>{ |
|
518 \begin{frame}[c] |
|
519 |
|
520 \begin{center} |
|
521 \begin{tabular}[b]{ll} |
|
522 \bl{r$^*$} & \includegraphics[scale=0.7]{pics/star.jpg}\\ |
|
523 \end{tabular} |
|
524 \end{center}\pause\bigskip |
|
525 |
|
526 Why can't we just have an epsilon transition from the accepting states to the starting state? |
|
527 |
|
528 \end{frame}} |
|
529 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
530 |
|
531 |
|
532 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
533 \mode<presentation>{ |
|
534 \begin{frame}[c] |
|
535 \frametitle{\begin{tabular}{c}Subset Construction\end{tabular}} |
|
536 |
|
537 |
|
538 \begin{textblock}{5}(1,2.5) |
|
539 \includegraphics[scale=0.5]{pics/ch5.jpg} |
|
540 \end{textblock} |
|
541 |
|
542 \begin{textblock}{11}(6.5,4.5) |
|
543 \begin{tabular}{r|cl} |
|
544 & a & b\\ |
|
545 \hline |
|
546 $\varnothing$ \onslide<2>{\textcolor{white}{*}} & $\varnothing$ & $\varnothing$\\ |
|
547 $\{0\}$ \onslide<2>{\textcolor{white}{*}} & $\{0,1,2\}$ & $\{2\}$\\ |
|
548 $\{1\}$ \onslide<2>{\textcolor{white}{*}} &$\{1\}$ & $\varnothing$\\ |
|
549 $\{2\}$ \onslide<2>{*} & $\varnothing$ &$\{2\}$\\ |
|
550 $\{0,1\}$ \onslide<2>{\textcolor{white}{*}} &$\{0,1,2\}$ &$\{2\}$\\ |
|
551 $\{0,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ |
|
552 $\{1,2\}$ \onslide<2>{*}& $\{1\}$ & $\{2\}$\\ |
|
553 \onslide<2>{s:} $\{0,1,2\}$ \onslide<2>{*}&$\{0,1,2\}$ &$\{2\}$\\ |
|
554 \end{tabular} |
|
555 \end{textblock} |
|
556 |
|
557 |
|
558 \end{frame}} |
|
559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
560 |
|
561 |
|
562 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
563 \mode<presentation>{ |
|
564 \begin{frame}[c] |
|
565 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
|
566 |
|
567 A language is \alert{regular} iff there exists |
|
568 a regular expression that recognises all its strings.\bigskip\medskip |
|
569 |
|
570 or equivalently\bigskip\medskip |
|
571 |
|
572 A language is \alert{regular} iff there exists |
|
573 a deterministic finite automaton that recognises all its strings.\bigskip\pause |
|
574 |
|
575 Why is every finite set of strings a regular language? |
|
576 \end{frame}} |
|
577 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
578 |
|
579 |
|
580 |
|
581 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
582 \mode<presentation>{ |
|
583 \begin{frame}[c] |
|
584 |
|
585 \begin{center} |
|
586 \includegraphics[scale=0.5]{pics/ch3.jpg} |
|
587 \end{center} |
|
588 |
|
589 \begin{center} |
|
590 \includegraphics[scale=0.5]{pics/ch4.jpg}\\ |
|
591 minimal automaton |
|
592 \end{center} |
|
593 |
|
594 \end{frame}} |
|
595 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
596 |
|
597 |
|
598 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
599 \mode<presentation>{ |
|
600 \begin{frame}[c] |
|
601 |
|
602 \begin{enumerate} |
|
603 \item Take all pairs \bl{(q, p)} with \bl{q $\not=$ p} |
|
604 \item Mark all pairs that accepting and non-accepting states |
|
605 \item For all unmarked pairs \bl{(q, p)} and all characters \bl{c} tests wether |
|
606 \begin{center} |
|
607 \bl{($\delta$(q,c), $\delta$(p,c))} |
|
608 \end{center} |
|
609 are marked. If yes, then also mark \bl{(q, p)} |
|
610 \item Repeat last step until no chance. |
|
611 \item All unmarked pairs can be merged. |
|
612 \end{enumerate} |
|
613 |
|
614 \end{frame}} |
|
615 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
616 |
|
617 |
|
618 |
|
619 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
620 \mode<presentation>{ |
|
621 \begin{frame}[c] |
|
622 |
|
623 Given the function |
|
624 |
|
625 \begin{center} |
|
626 \bl{\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} |
|
627 $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ |
|
628 $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ |
|
629 $rev(c)$ & $\dn$ & $c$\\ |
|
630 $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ |
|
631 $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ |
|
632 $rev(r^*)$ & $\dn$ & $rev(r)^*$\\ |
|
633 \end{tabular}} |
|
634 \end{center} |
|
635 |
|
636 |
|
637 and the set |
|
638 |
|
639 \begin{center} |
|
640 \bl{$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$} |
|
641 \end{center} |
|
642 |
|
643 prove whether |
|
644 |
|
645 \begin{center} |
|
646 \bl{$L(rev(r)) = Rev (L(r))$} |
|
647 \end{center} |
|
648 |
|
649 \end{frame}} |
|
650 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
651 |
|
652 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
653 \mode<presentation>{ |
|
654 \begin{frame}[c] |
|
655 |
|
656 \begin{itemize} |
|
657 \item The star-case in our proof about the matcher needs the following lemma |
|
658 \begin{center} |
|
659 \bl{Der\,c\,A$^*$ $=$ (Der c A)\,@\, A$^*$} |
|
660 \end{center} |
|
661 \end{itemize}\bigskip\bigskip |
|
662 |
|
663 \begin{itemize} |
|
664 \item If \bl{\texttt{""} $\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B $\cup$ (Der\,c\,B)}\medskip |
|
665 \item If \bl{\texttt{""} $\not\in$ A}, then\\ \bl{Der\,c\,(A @ B) $=$ (Der\,c\,A) @ B} |
|
666 |
|
667 \end{itemize} |
|
668 |
|
669 \end{frame}} |
|
670 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
671 |
|
672 |
|
673 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
674 \mode<presentation>{ |
|
675 \begin{frame}[c] |
|
676 |
|
677 \begin{itemize} |
|
678 \item Assuming you have the alphabet \bl{\{a, b, c\}}\bigskip |
|
679 \item Give a regular expression that can recognise all strings that have at least one \bl{b}. |
|
680 \end{itemize} |
|
681 |
|
682 \end{frame}} |
|
683 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
684 |
|
685 |
|
686 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
687 \mode<presentation>{ |
|
688 \begin{frame}[c] |
|
689 |
|
690 ``I hate coding. I do not want to look at code.'' |
|
691 |
|
692 \end{frame}} |
|
693 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
694 |
|
695 |
857 |
696 |
858 |
697 \end{document} |
859 \end{document} |
698 |
860 |
699 %%% Local Variables: |
861 %%% Local Variables: |