429 \end{center} |
429 \end{center} |
430 |
430 |
431 \end{frame}} |
431 \end{frame}} |
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
432 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
433 |
433 |
434 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
435 \mode<presentation>{ |
|
436 \begin{frame}[c] |
|
437 \frametitle{\begin{tabular}{c}Nullability\end{tabular}} |
|
438 |
|
439 \small |
|
440 whether a regular expression matches the empty string:\medskip |
|
441 |
|
442 |
|
443 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
444 \texttt{\lstinputlisting{app5.scala}}} |
|
445 |
|
446 |
|
447 |
|
448 \end{frame}} |
|
449 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
450 |
|
451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
452 \mode<presentation>{ |
|
453 \begin{frame}[c] |
|
454 \frametitle{\begin{tabular}{c}Derivative of a Rexp\end{tabular}} |
|
455 |
|
456 \large |
|
457 If \bl{r} matches the string \bl{c::s}, what is a regular expression that matches \bl{s}?\bigskip\bigskip\bigskip\bigskip |
|
458 |
|
459 \small |
|
460 \bl{der c r} gives the answer |
|
461 \end{frame}} |
|
462 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
463 |
|
464 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
465 \mode<presentation>{ |
|
466 \begin{frame}[c] |
|
467 \frametitle{\begin{tabular}{c}The Derivative\end{tabular}} |
|
468 |
|
469 \begin{center} |
|
470 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}} |
|
471 \bl{der c ($\varnothing$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
|
472 \bl{der c ($\epsilon$)} & \bl{$\dn$} & \bl{$\varnothing$} & \\ |
|
473 \bl{der c (d)} & \bl{$\dn$} & \bl{if c $=$ d then [] else $\varnothing$} & \\ |
|
474 \bl{der c (r$_1$ + r$_2$)} & \bl{$\dn$} & \bl{(der c r$_1$) + (der c r$_2$)} & \\ |
|
475 \bl{der c (r$_1$ $\cdot$ r$_2$)} & \bl{$\dn$} & \bl{((der c r$_1$) $\cdot$ r$_2$) + } & \\ |
|
476 & & \bl{\hspace{3mm}(if nullable r$_1$ then der c r$_2$ else $\varnothing$)}\\ |
|
477 \bl{der c (r$^*$)} & \bl{$\dn$} & \bl{(der c r) $\cdot$ (r$^*$)} &\smallskip\\\pause |
|
478 |
|
479 \bl{ders [] r} & \bl{$\dn$} & \bl{r} & \\ |
|
480 \bl{ders (c::s) r} & \bl{$\dn$} & \bl{ders s (der c r)} & \\ |
|
481 \end{tabular} |
|
482 \end{center} |
|
483 |
|
484 \end{frame}} |
|
485 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
486 |
|
487 |
|
488 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
489 \mode<presentation>{ |
|
490 \begin{frame}[c] |
|
491 \frametitle{\begin{tabular}{c}The Derivative\end{tabular}} |
|
492 |
|
493 |
|
494 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
495 \texttt{\lstinputlisting{app6.scala}}} |
|
496 |
|
497 |
|
498 |
|
499 \end{frame}} |
|
500 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
501 |
|
502 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
503 \mode<presentation>{ |
|
504 \begin{frame}[c] |
|
505 \frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}} |
|
506 |
|
507 |
|
508 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
|
509 \texttt{\lstinputlisting{app7.scala}}} |
|
510 |
|
511 |
|
512 |
|
513 \end{frame}} |
|
514 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
515 |
|
516 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
434 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
517 \mode<presentation>{ |
435 \mode<presentation>{ |
518 \begin{frame}[c] |
436 \begin{frame}[c] |
519 \frametitle{\begin{tabular}{c}This Course\end{tabular}} |
437 \frametitle{\begin{tabular}{c}This Course\end{tabular}} |
520 |
438 |
521 We will have a look at |
439 We will have a look at: |
522 |
440 |
523 \begin{itemize} |
441 \begin{itemize} |
524 \item regular expression / regular expression matching |
442 \item regular expressions / regular expression matching |
525 \item a bit of sets (of strings) |
|
526 \item automata |
443 \item automata |
527 \item the Myhill-Nerode theorem |
444 \item the Myhill-Nerode theorem |
528 \item parsing |
445 \item parsing |
529 \item grammars |
446 \item grammars |
530 \item a small interpreter / webbrowser |
447 \item a small interpreter / web browser |
531 \end{itemize} |
448 \end{itemize} |
532 |
449 |
533 \end{frame}} |
450 \end{frame}} |
534 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
451 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
535 |
452 |
539 \mode<presentation>{ |
456 \mode<presentation>{ |
540 \begin{frame}[c] |
457 \begin{frame}[c] |
541 \frametitle{\begin{tabular}{c}Exam\end{tabular}} |
458 \frametitle{\begin{tabular}{c}Exam\end{tabular}} |
542 |
459 |
543 \begin{itemize} |
460 \begin{itemize} |
544 \item The question ``Is this relevant for the exams?'' is not appreciated!\bigskip\\ |
461 \item The question ``Is this relevant for the exam?'' is not appreciated!\bigskip\\ |
545 |
462 |
546 Whatever is in the homework sheets (and is not marked optional) is relevant for the |
463 Whatever is in the homework sheets (and is not marked optional) is relevant for the |
547 exam.\\ No code needs to be written. |
464 exam.\\ No code needs to be written. |
548 \end{itemize} |
465 \end{itemize} |
549 |
466 |
550 \end{frame}} |
467 \end{frame}} |
551 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
468 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
552 |
|
553 |
|
554 |
|
555 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
556 \mode<presentation>{ |
|
557 \begin{frame}[t] |
|
558 \frametitle{\begin{tabular}{c}Maps in Scala\end{tabular}} |
|
559 |
|
560 \begin{itemize} |
|
561 \item {\bf\texttt{map}} takes a function, say f, and applies it to every element of the list: |
|
562 \end{itemize} |
|
563 |
|
564 \begin{textblock}{15}(2,7) |
|
565 \fontsize{13}{14}\selectfont |
|
566 \bf\texttt{List(1, 2, 3, 4, 5, 6, 7, 8, 9)} |
|
567 \end{textblock} |
|
568 |
|
569 \begin{textblock}{15}(2,10) |
|
570 \fontsize{13}{14}\selectfont |
|
571 \bf\texttt{List(1, 4, 9, 16, 25, 36, 49, 64, 81)} |
|
572 \end{textblock} |
|
573 |
|
574 \end{frame}} |
|
575 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
576 |
469 |
577 |
470 |
578 \end{document} |
471 \end{document} |
579 |
472 |
580 %%% Local Variables: |
473 %%% Local Variables: |