481 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
541 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
482 |
542 |
483 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
543 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
484 \mode<presentation>{ |
544 \mode<presentation>{ |
485 \begin{frame}[c] |
545 \begin{frame}[c] |
486 \frametitle{\begin{tabular}{c}The Rexp Matcher\end{tabular}} |
546 \frametitle{\begin{tabular}{c}Examples\end{tabular}} |
487 |
547 |
488 |
548 Given \bl{$r \dn ((a \cdot b) + b)^*$} what is |
489 {\lstset{language=Scala}\fontsize{8}{10}\selectfont |
549 |
490 \texttt{\lstinputlisting{../progs/app7.scala}}} |
550 \begin{center} |
491 |
551 \begin{tabular}{l} |
|
552 \bl{$der\,a\,r$}\\ |
|
553 \bl{$der\,b\,r$} |
|
554 \end{tabular} |
|
555 \end{center} |
492 |
556 |
493 |
557 |
494 \end{frame}} |
558 \end{frame}} |
495 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
559 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
496 |
560 |
497 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
561 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
498 \mode<presentation>{ |
562 \mode<presentation>{ |
499 \begin{frame}[t] |
563 \begin{frame}[t] |
500 \frametitle{\begin{tabular}{c}Proofs about Rexp\end{tabular}} |
564 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
565 |
|
566 \mbox{}\\[-13mm] |
|
567 |
|
568 \begin{tikzpicture}[y=.2cm, x=.3cm] |
|
569 %axis |
|
570 \draw (0,0) -- coordinate (x axis mid) (30,0); |
|
571 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
572 %ticks |
|
573 \foreach \x in {0,5,...,30} |
|
574 \draw (\x,1pt) -- (\x,-3pt) |
|
575 node[anchor=north] {\x}; |
|
576 \foreach \y in {0,5,...,30} |
|
577 \draw (1pt,\y) -- (-3pt,\y) |
|
578 node[anchor=east] {\y}; |
|
579 %labels |
|
580 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
581 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
582 |
|
583 %plots |
|
584 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
585 file {re-python.data}; |
|
586 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
587 file {re1.data}; |
|
588 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
589 file {re-ruby.data}; |
|
590 |
|
591 |
|
592 %legend |
|
593 \begin{scope}[shift={(4,20)}] |
|
594 \draw[color=blue] (0,0) -- |
|
595 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
596 node[right]{\small Python}; |
|
597 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
598 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
599 node[right]{\small Ruby}; |
|
600 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
601 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
602 node[right]{\small Scala V1}; |
|
603 \end{scope} |
|
604 \end{tikzpicture} |
|
605 |
|
606 \end{frame}} |
|
607 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
608 |
|
609 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
610 \mode<presentation>{ |
|
611 \begin{frame}[t] |
|
612 \frametitle{\begin{tabular}{c}Proofs about Rexps\end{tabular}} |
501 |
613 |
502 Remember their inductive definition:\\[5cm] |
614 Remember their inductive definition:\\[5cm] |
503 |
615 |
504 \begin{textblock}{6}(5,5) |
616 \begin{textblock}{6}(5,5) |
505 \begin{tabular}{@ {}rrl} |
617 \begin{tabular}{@ {}rrl} |
506 \bl{r} & \bl{$::=$} & \bl{$\varnothing$}\\ |
618 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$}\\ |
507 & \bl{$\mid$} & \bl{$\epsilon$} \\ |
619 & \bl{$\mid$} & \bl{$\epsilon$} \\ |
508 & \bl{$\mid$} & \bl{c} \\ |
620 & \bl{$\mid$} & \bl{$c$} \\ |
509 & \bl{$\mid$} & \bl{r$_1$ $\cdot$ r$_2$}\\ |
621 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ |
510 & \bl{$\mid$} & \bl{r$_1$ + r$_2$} \\ |
622 & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ |
511 & \bl{$\mid$} & \bl{r$^*$} \\ |
623 & \bl{$\mid$} & \bl{$r^*$} \\ |
512 \end{tabular} |
624 \end{tabular} |
513 \end{textblock} |
625 \end{textblock} |
514 |
626 |
515 If we want to prove something, say a property \bl{$P$(r)}, for all regular expressions \bl{r} then \ldots |
627 If we want to prove something, say a property \bl{$P(r)$}, for all regular expressions \bl{$r$} then \ldots |
516 |
628 |
517 \end{frame}} |
629 \end{frame}} |
518 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
630 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
519 |
631 |
520 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
632 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
541 \frametitle{\begin{tabular}{c}Proofs about Rexp (3)\end{tabular}} |
653 \frametitle{\begin{tabular}{c}Proofs about Rexp (3)\end{tabular}} |
542 |
654 |
543 Assume \bl{$P(r)$} is the property: |
655 Assume \bl{$P(r)$} is the property: |
544 |
656 |
545 \begin{center} |
657 \begin{center} |
546 \bl{nullable(r)} if and only if \bl{"" $\in$ $L$(r)} |
658 \bl{$nullable(r)$} if and only if \bl{$"" \in L(r)$} |
547 \end{center} |
659 \end{center} |
548 |
660 |
549 \end{frame}} |
661 \end{frame}} |
550 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
662 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
551 |
663 |
552 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
664 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
553 \mode<presentation>{ |
665 \mode<presentation>{ |
554 \begin{frame}[c] |
666 \begin{frame}[c] |
|
667 \frametitle{\begin{tabular}{c}Proofs about Rexp (4)\end{tabular}} |
|
668 |
|
669 Let \bl{$Der\,c\,A$} be the set defined as |
|
670 |
|
671 \begin{center} |
|
672 \bl{$Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ } |
|
673 \end{center} |
|
674 |
|
675 We can prove |
|
676 |
|
677 \begin{center} |
|
678 \bl{$L(der\,c\,r) = Der\,c\,(L(r))$} |
|
679 \end{center} |
|
680 |
|
681 by induction on \bl{$r$}. |
|
682 |
|
683 \end{frame}} |
|
684 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
685 |
|
686 |
|
687 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
688 \mode<presentation>{ |
|
689 \begin{frame}[c] |
555 \frametitle{\begin{tabular}{c}Proofs about Strings\end{tabular}} |
690 \frametitle{\begin{tabular}{c}Proofs about Strings\end{tabular}} |
556 |
691 |
557 If we want to prove something, say a property \bl{$P$(s)}, for all strings \bl{s} then \ldots\bigskip |
692 If we want to prove something, say a property \bl{$P(s)$}, for all strings \bl{$s$} then \ldots\bigskip |
558 |
693 |
559 \begin{itemize} |
694 \begin{itemize} |
560 \item \bl{$P$} holds for the empty string, and\medskip |
695 \item \bl{$P$} holds for the empty string, and\medskip |
561 \item \bl{$P$} holds for the string \bl{c::s} under the assumption that \bl{$P$} |
696 \item \bl{$P$} holds for the string \bl{$c\!::\!s$} under the assumption that \bl{$P$} |
562 already holds for \bl{s} |
697 already holds for \bl{$s$} |
563 \end{itemize} |
698 \end{itemize} |
564 \end{frame}} |
699 \end{frame}} |
565 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
700 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
566 |
701 |
567 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
702 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
568 \mode<presentation>{ |
703 \mode<presentation>{ |
569 \begin{frame}[c] |
704 \begin{frame}[c] |
570 \frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}} |
705 \frametitle{\begin{tabular}{c}Proofs about Strings (2)\end{tabular}} |
571 |
706 |
572 Let \bl{Der c A} be the set defined as |
707 We can finally prove |
573 |
708 |
574 \begin{center} |
709 \begin{center} |
575 \bl{Der c A $\dn$ $\{$ s $|$ c::s $\in$ A$\}$ } |
710 \bl{$matcher(r, s)$} if and only if \bl{$s \in L(r)$} |
576 \end{center} |
711 \end{center} |
577 |
712 |
578 Assume that \bl{$L$(der c r) = Der c ($L$(r))}. Prove that |
713 |
579 |
714 \end{frame}} |
580 \begin{center} |
715 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
581 \bl{matcher(r, s) if and only if s $\in$ $L$(r)} |
716 |
|
717 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
718 \mode<presentation>{ |
|
719 \begin{frame}[t] |
|
720 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
721 |
|
722 \mbox{}\\[-13mm] |
|
723 |
|
724 \begin{tikzpicture}[y=.2cm, x=.3cm] |
|
725 %axis |
|
726 \draw (0,0) -- coordinate (x axis mid) (30,0); |
|
727 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
728 %ticks |
|
729 \foreach \x in {0,5,...,30} |
|
730 \draw (\x,1pt) -- (\x,-3pt) |
|
731 node[anchor=north] {\x}; |
|
732 \foreach \y in {0,5,...,30} |
|
733 \draw (1pt,\y) -- (-3pt,\y) |
|
734 node[anchor=east] {\y}; |
|
735 %labels |
|
736 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
737 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
738 |
|
739 %plots |
|
740 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
741 file {re-python.data}; |
|
742 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
743 file {re1.data}; |
|
744 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
745 file {re-ruby.data}; |
|
746 |
|
747 |
|
748 %legend |
|
749 \begin{scope}[shift={(4,20)}] |
|
750 \draw[color=blue] (0,0) -- |
|
751 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
752 node[right]{\small Python}; |
|
753 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
754 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
755 node[right]{\small Ruby}; |
|
756 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
757 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
758 node[right]{\small Scala V1}; |
|
759 \end{scope} |
|
760 \end{tikzpicture} |
|
761 |
|
762 \end{frame}} |
|
763 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
764 |
|
765 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
766 \mode<presentation>{ |
|
767 \begin{frame}[c] |
|
768 \frametitle{\begin{tabular}{c}Problem\end{tabular}} |
|
769 |
|
770 We represented ``n-times'' as a sequence regular expression: |
|
771 |
|
772 \begin{center} |
|
773 \begin{tabular}{ll} |
|
774 1: |
|
775 \end{tabular} |
582 \end{center} |
776 \end{center} |
583 |
777 |
584 |
778 \end{frame}} |
585 \end{frame}} |
779 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
586 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
780 |
|
781 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
782 \mode<presentation>{ |
|
783 \begin{frame}[t] |
|
784 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
785 |
|
786 \mbox{}\\[-13mm] |
|
787 |
|
788 \begin{tikzpicture}[y=.2cm, x=.12cm] |
|
789 %axis |
|
790 \draw (0,0) -- coordinate (x axis mid) (70,0); |
|
791 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
792 %ticks |
|
793 \foreach \x in {0,10,...,70} |
|
794 \draw (\x,1pt) -- (\x,-3pt) |
|
795 node[anchor=north] {\x}; |
|
796 \foreach \y in {0,5,...,30} |
|
797 \draw (1pt,\y) -- (-3pt,\y) |
|
798 node[anchor=east] {\y}; |
|
799 %labels |
|
800 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
801 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
802 |
|
803 %plots |
|
804 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
805 file {re-python.data}; |
|
806 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
807 file {re1.data}; |
|
808 \draw[color=green] plot[mark=square*, mark options={fill=white} ] |
|
809 file {re2a.data}; |
|
810 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
811 file {re-ruby.data}; |
|
812 |
|
813 %legend |
|
814 \begin{scope}[shift={(4,20)}] |
|
815 \draw[color=blue] (0,0) -- |
|
816 plot[mark=*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
817 node[right]{\small Python}; |
|
818 \draw[yshift=-\baselineskip, color=brown] (0,0) -- |
|
819 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
820 node[right]{\small Ruby}; |
|
821 \draw[yshift=\baselineskip, color=red] (0,0) -- |
|
822 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
823 node[right]{\small Scala V1}; |
|
824 \draw[yshift=2\baselineskip, color=green] (0,0) -- |
|
825 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (0.5,0) |
|
826 node[right]{\small Scala V2}; |
|
827 \end{scope} |
|
828 \end{tikzpicture} |
|
829 |
|
830 \end{frame}} |
|
831 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
832 |
|
833 |
|
834 |
|
835 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
836 \mode<presentation>{ |
|
837 \begin{frame}[t] |
|
838 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
839 |
|
840 \mbox{}\\[-13mm] |
|
841 |
|
842 \begin{tabular}{@ {\hspace{-5mm}}l} |
|
843 \begin{tikzpicture}[y=.2cm, x=.01cm] |
|
844 %axis |
|
845 \draw (0,0) -- coordinate (x axis mid) (1000,0); |
|
846 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
847 %ticks |
|
848 \foreach \x in {0,100,...,1000} |
|
849 \draw (\x,1pt) -- (\x,-3pt) |
|
850 node[anchor=north] {\x}; |
|
851 \foreach \y in {0,5,...,30} |
|
852 \draw (1pt,\y) -- (-3pt,\y) |
|
853 node[anchor=east] {\y}; |
|
854 %labels |
|
855 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
856 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
857 |
|
858 %plots |
|
859 \draw[color=blue] plot[mark=*, mark options={fill=white}] |
|
860 file {re-python.data}; |
|
861 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
862 file {re1.data}; |
|
863 \draw[color=green] plot[mark=square*, mark options={fill=white} ] |
|
864 file {re2b.data}; |
|
865 \draw[color=brown] plot[mark=pentagon*, mark options={fill=white} ] |
|
866 file {re-ruby.data}; |
|
867 |
|
868 %legend |
|
869 \begin{scope}[shift={(100,20)}] |
|
870 \draw[color=blue] (0,0) -- |
|
871 plot[mark=*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
872 node[right]{\small Python}; |
|
873 \draw[yshift=-13, color=brown] (0,0) -- |
|
874 plot[mark=pentagon*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
875 node[right]{\small Ruby}; |
|
876 \draw[yshift=13, color=red] (0,0) -- |
|
877 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
878 node[right]{\small Scala V1}; |
|
879 \draw[yshift=26, color=green] (0,0) -- |
|
880 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
881 node[right]{\small Scala V2}; |
|
882 \end{scope} |
|
883 \end{tikzpicture} |
|
884 \end{tabular} |
|
885 |
|
886 \end{frame}} |
|
887 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
888 |
587 |
889 |
588 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
890 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
589 \mode<presentation>{ |
891 \mode<presentation>{ |
590 \begin{frame}[c] |
892 \begin{frame}[c] |
591 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
893 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |