911 \end{tabular} |
939 \end{tabular} |
912 |
940 |
913 \end{frame}} |
941 \end{frame}} |
914 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
942 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
915 |
943 |
|
944 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
945 \mode<presentation>{ |
|
946 \begin{frame}[c] |
|
947 \frametitle{\begin{tabular}{c}Examples\end{tabular}} |
|
948 |
|
949 Recall the example of \bl{$r \dn ((a \cdot b) + b)^*$} with |
|
950 |
|
951 \begin{center} |
|
952 \begin{tabular}{l} |
|
953 \bl{$der\,a\,r = ((\epsilon \cdot b) + \varnothing) \cdot r$}\\ |
|
954 \bl{$der\,b\,r = ((\varnothing \cdot b) + \epsilon)\cdot r$} |
|
955 \end{tabular} |
|
956 \end{center} |
|
957 |
|
958 What are these regular expressions equal to? |
|
959 |
|
960 \end{frame}} |
|
961 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
962 |
|
963 |
|
964 |
|
965 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
966 \mode<presentation>{ |
|
967 \begin{frame}[t] |
|
968 \frametitle{\begin{tabular}{c}\bl{$(a?\{n\}) \cdot a\{n\}$}\end{tabular}} |
|
969 |
|
970 \mbox{}\\[-9mm] |
|
971 |
|
972 \begin{tabular}{@ {\hspace{-5mm}}l} |
|
973 \begin{tikzpicture}[y=.2cm, x=.0008cm] |
|
974 %axis |
|
975 \draw (0,0) -- coordinate (x axis mid) (12000,0); |
|
976 \draw (0,0) -- coordinate (y axis mid) (0,30); |
|
977 %ticks |
|
978 \foreach \x in {0,2000,...,12000} |
|
979 \draw (\x,1pt) -- (\x,-3pt) |
|
980 node[anchor=north] {\x}; |
|
981 \foreach \y in {0,5,...,30} |
|
982 \draw (1pt,\y) -- (-3pt,\y) |
|
983 node[anchor=east] {\y}; |
|
984 %labels |
|
985 \node[below=0.6cm] at (x axis mid) {\bl{a}s}; |
|
986 \node[rotate=90, left=1.2cm] at (y axis mid) {secs}; |
|
987 |
|
988 %plots |
|
989 \draw[color=red] plot[mark=triangle*, mark options={fill=white} ] |
|
990 file {re1.data}; |
|
991 \draw[color=green] plot[mark=square*, mark options={fill=white} ] |
|
992 file {re2b.data}; |
|
993 \draw[color=black] plot[mark=square*, mark options={fill=white} ] |
|
994 file {re3.data}; |
|
995 |
|
996 %legend |
|
997 \begin{scope}[shift={(2000,20)}] |
|
998 \draw[color=red] (0,0) -- |
|
999 plot[mark=triangle*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
1000 node[right]{\small Scala V1}; |
|
1001 \draw[yshift=13, color=green] (0,0) -- |
|
1002 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
1003 node[right]{\small Scala V2}; |
|
1004 \draw[yshift=26, color=black] (0,0) -- |
|
1005 plot[mark=square*, mark options={fill=white}] (0.25,0) -- (50,0) |
|
1006 node[right]{\small Scala V3}; |
|
1007 \end{scope} |
|
1008 \end{tikzpicture} |
|
1009 \end{tabular} |
|
1010 |
|
1011 \end{frame}} |
|
1012 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1013 |
916 |
1014 |
917 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1015 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
918 \mode<presentation>{ |
1016 \mode<presentation>{ |
919 \begin{frame}[c] |
1017 \begin{frame}[c] |
920 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
1018 \frametitle{\begin{tabular}{c}Regular Languages\end{tabular}} |
921 |
1019 |
922 A language (set of strings) is \alert{regular} iff there exists |
1020 A language (a set of strings) is \alert{regular} iff there exists |
923 a regular expression that recognises all its strings. |
1021 a regular expression that recognises all its strings.\bigskip\bigskip\pause |
924 |
1022 |
|
1023 |
|
1024 Do you think there are languages that are {\bf not} regular? |
925 \end{frame}} |
1025 \end{frame}} |
926 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1026 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
927 |
1027 |
928 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1028 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
929 \mode<presentation>{ |
1029 \mode<presentation>{ |