8 |
8 |
9 \pgfplotsset{compat=1.11} |
9 \pgfplotsset{compat=1.11} |
10 |
10 |
11 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
11 \newcommand{\bl}[1]{\textcolor{blue}{#1}} |
12 |
12 |
13 \renewcommand{\slidecaption}{AFL 04, King's College London} |
13 \renewcommand{\slidecaption}{CFL 04, King's College London} |
14 |
14 |
15 \begin{document} |
15 \begin{document} |
16 |
16 |
17 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
17 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
18 \begin{frame}[t] |
18 \begin{frame}[t] |
19 \frametitle{% |
19 \frametitle{% |
20 \begin{tabular}{@ {}c@ {}} |
20 \begin{tabular}{@ {}c@ {}} |
21 \\[-3mm] |
21 \\[-3mm] |
22 \LARGE Automata and \\[-2mm] |
22 \LARGE Compilers and \\[-2mm] |
23 \LARGE Formal Languages (4)\\[3mm] |
23 \LARGE Formal Languages (4)\\[3mm] |
24 \end{tabular}} |
24 \end{tabular}} |
25 |
25 |
26 \normalsize |
26 \normalsize |
27 \begin{center} |
27 \begin{center} |
75 width=10cm, |
75 width=10cm, |
76 height=7cm, |
76 height=7cm, |
77 legend entries={Python,Ruby,my NFA}, |
77 legend entries={Python,Ruby,my NFA}, |
78 legend pos=north west, |
78 legend pos=north west, |
79 legend cell align=left] |
79 legend cell align=left] |
80 \addplot[blue,mark=*, mark options={fill=white}] |
80 \addplot[blue,mark=*, mark options={fill=white}] table {re-python.data}; |
81 table {re-python.data}; |
81 \addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data}; |
82 \addplot[brown,mark=pentagon*, mark options={fill=white}] |
82 \addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data}; |
83 table {re-ruby.data}; |
|
84 \addplot[red,mark=triangle*, mark options={fill=white}] |
|
85 table {nfasearch.data}; |
|
86 \end{axis} |
83 \end{axis} |
87 \end{tikzpicture} |
84 \end{tikzpicture} |
88 |
85 |
89 \end{frame} |
86 \end{frame} |
90 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
87 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
109 \end{tikzpicture} |
106 \end{tikzpicture} |
110 \end{center}\bigskip |
107 \end{center}\bigskip |
111 |
108 |
112 \begin{center} |
109 \begin{center} |
113 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} |
110 \begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l@{\hspace{7mm}}l} |
114 \bl{$q_0$} & \bl{$=$} & \bl{$\epsilon + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ |
111 \bl{$q_0$} & \bl{$=$} & \bl{$\ONE + q_0\,b + q_1\,b + q_2\,b$} & (start state)\\ |
115 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
112 \bl{$q_1$} & \bl{$=$} & \bl{$q_0\,a$}\\ |
116 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
113 \bl{$q_2$} & \bl{$=$} & \bl{$q_1\,a + q_2\,a$}\\ |
117 |
114 |
118 \end{tabular} |
115 \end{tabular} |
119 \end{center} |
116 \end{center} |
540 |
537 |
541 \begin{center} |
538 \begin{center} |
542 \begin{columns} |
539 \begin{columns} |
543 \begin{column}{3cm} |
540 \begin{column}{3cm} |
544 \begin{tabular}{@{}rrl@{}} |
541 \begin{tabular}{@{}rrl@{}} |
545 \bl{$r$} & \bl{$::=$} & \bl{$\varnothing$}\\ |
542 \bl{$r$} & \bl{$::=$} & \bl{$\ZERO$}\\ |
546 & \bl{$\mid$} & \bl{$\epsilon$} \\ |
543 & \bl{$\mid$} & \bl{$\ONE$} \\ |
547 & \bl{$\mid$} & \bl{$c$} \\ |
544 & \bl{$\mid$} & \bl{$c$} \\ |
548 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ |
545 & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}\\ |
549 & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ |
546 & \bl{$\mid$} & \bl{$r_1 + r_2$} \\ |
550 \\ |
547 \\ |
551 & \bl{$\mid$} & \bl{$r^*$} \\ |
548 & \bl{$\mid$} & \bl{$r^*$} \\ |
587 |
584 |
588 Finding a (posix) value for recognising the empty string: |
585 Finding a (posix) value for recognising the empty string: |
589 |
586 |
590 \begin{center} |
587 \begin{center} |
591 \begin{tabular}{lcl} |
588 \begin{tabular}{lcl} |
592 \bl{$mkeps\,\epsilon$} & \bl{$\dn$} & \bl{$Empty$}\\ |
589 \bl{$mkeps\,\ONE$} & \bl{$\dn$} & \bl{$Empty$}\\ |
593 \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
590 \bl{$mkeps\,r_1 + r_2$} & \bl{$\dn$} & \bl{if $nullable(r_1)$} \\ |
594 & & \bl{then $Left(mkeps(r_1))$}\\ |
591 & & \bl{then $Left(mkeps(r_1))$}\\ |
595 & & \bl{else $Right(mkeps(r_2))$}\\ |
592 & & \bl{else $Right(mkeps(r_2))$}\\ |
596 \bl{$mkeps\,r_1 \cdot r_2$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ |
593 \bl{$mkeps\,r_1 \cdot r_2$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\ |
597 \bl{$mkeps\,r^*$} & \bl{$\dn$} & \bl{$[]$} \\ |
594 \bl{$mkeps\,r^*$} & \bl{$\dn$} & \bl{$[]$} \\ |
733 \begin{textblock}{6}(1,0.8) |
730 \begin{textblock}{6}(1,0.8) |
734 \begin{bubble}[6cm] |
731 \begin{bubble}[6cm] |
735 \small |
732 \small |
736 \begin{tabular}{ll} |
733 \begin{tabular}{ll} |
737 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ |
734 \bl{$r_1$}: & \bl{$a \cdot (b \cdot c)$}\\ |
738 \bl{$r_2$}: & \bl{$\epsilon \cdot (b \cdot c)$}\\ |
735 \bl{$r_2$}: & \bl{$\ONE \cdot (b \cdot c)$}\\ |
739 \bl{$r_3$}: & \bl{$(\varnothing \cdot (b \cdot c)) + (\epsilon \cdot c)$}\\ |
736 \bl{$r_3$}: & \bl{$(\ZERO \cdot (b \cdot c)) + (\ONE \cdot c)$}\\ |
740 \bl{$r_4$}: & \bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$}\\ |
737 \bl{$r_4$}: & \bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$}\\ |
741 \end{tabular} |
738 \end{tabular} |
742 \end{bubble} |
739 \end{bubble} |
743 \end{textblock} |
740 \end{textblock} |
744 |
741 |
745 \begin{textblock}{6}(1,11.4) |
742 \begin{textblock}{6}(1,11.4) |
829 \small |
826 \small |
830 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} |
827 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} |
831 |
828 |
832 \end{frame} |
829 \end{frame} |
833 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
830 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
834 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
831 |
835 \begin{frame}[c] |
832 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
836 \frametitle{Records} |
833 \begin{frame}[c] |
837 |
834 |
838 \begin{itemize} |
835 \begin{itemize} |
839 \item new regex: \bl{$(x:r)$}\hspace{7mm}new value: \bl{$Rec(x,v)$}\medskip\pause |
836 \item A regular expression for email addresses |
840 |
|
841 \item \bl{$nullable(x:r) \dn nullable(r)$} |
|
842 \item \bl{$der\,c\,(x:r) \dn (x:der\,c\,r)$} |
|
843 \item \bl{$mkeps(x:r) \dn Rec(x, mkeps(r))$} |
|
844 \item \bl{$inj\,(x:r)\,c\,v \dn Rec(x, inj\,r\,c\,v)$} |
|
845 \end{itemize}\bigskip\bigskip\pause |
|
846 |
|
847 \small |
|
848 for extracting subpatterns \bl{$(z: ((x:ab) + (y:ba))$} |
|
849 |
|
850 \end{frame} |
|
851 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
852 |
|
853 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
854 \begin{frame}[c] |
|
855 |
|
856 \begin{itemize} |
|
857 \item Regular expression for email addresses |
|
858 |
837 |
859 \begin{center} |
838 \begin{center} |
860 \begin{tabular}{l} |
839 \begin{tabular}{l} |
861 (name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\ |
840 (name: \bl{$[a\mbox{-}z0\mbox{-}9\_\!\_\,.-]^+$})\bl{$\cdot @\cdot$}\\ |
862 \qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,.-]^+$}) \bl{$\cdot .\cdot$}\\ |
841 \qquad(domain: \bl{$[a\mbox{-}z0\mbox{-}9\,.-]^+$}) \bl{$\cdot .\cdot$}\\ |
939 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
918 \draw (r4) node[anchor=north west] {\;\raisebox{-8mm}{\bl{$mkeps$}}}; |
940 \end{tikzpicture} |
919 \end{tikzpicture} |
941 \end{center} |
920 \end{center} |
942 |
921 |
943 \small |
922 \small |
944 \hspace{4.5cm}\bl{$(\varnothing \cdot (b \cdot c)) + ((\varnothing \cdot c) + \epsilon)$} |
923 \hspace{4.5cm}\bl{$(\ZERO \cdot (b \cdot c)) + ((\ZERO \cdot c) + \ONE)$} |
945 $\mapsto$ |
924 $\mapsto$ |
946 \bl{$\epsilon$} |
925 \bl{$\ONE$} |
947 |
926 |
948 \end{frame} |
927 \end{frame} |
949 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
928 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
950 |
929 |
951 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
930 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
952 \begin{frame}[c] |
931 \begin{frame}[c] |
953 \frametitle{Rectification} |
932 \frametitle{Rectification} |
954 |
933 |
955 \def\arraystretch{1.05} |
934 \def\arraystretch{1.05} |
956 \begin{center} |
935 \begin{center} |
957 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{5mm}}l} |
936 \begin{tabular}{l@{\hspace{2mm}}c@{\hspace{2mm}}l@{\hspace{8mm}}l} |
958 & & & \hspace{5mm}rectification \\ |
937 & & & \hspace{5mm}rectification \\ |
959 & & & \hspace{5mm}functions:\\ |
938 & & & \hspace{5mm}functions:\\ |
960 \bl{$r \cdot \varnothing$} & $\mapsto$ & \bl{$\varnothing$} & \\ |
939 \bl{$r \cdot \ZERO$} & $\mapsto$ & \bl{$\ZERO$} & \\ |
961 \bl{$\varnothing \cdot r$} & $\mapsto$ & \bl{$\varnothing$} & \\ |
940 \bl{$\ZERO \cdot r$} & $\mapsto$ & \bl{$\ZERO$} & \\ |
962 \bl{$r \cdot \epsilon$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\ |
941 \bl{$r \cdot \ONE$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,v, f_2\,Empty)$}\\ |
963 \bl{$\epsilon \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\ |
942 \bl{$\ONE \cdot r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Seq(f_1\,Empty, f_2\,v)$}\\ |
964 \bl{$r + \varnothing$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\ |
943 \bl{$r + \ZERO$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$}\\ |
965 \bl{$\varnothing + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\ |
944 \bl{$\ZERO + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Right(f_2\,v)$}\\ |
966 \bl{$r + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$} |
945 \bl{$r + r$} & $\mapsto$ & \bl{$r$} & \bl{$\lambda f_1\,f_2\,v.\, Left(f_1\,v)$} |
967 \end{tabular} |
946 \end{tabular} |
968 \end{center}\medskip\pause |
947 \end{center}\medskip\pause |
969 |
948 |
970 \small |
949 \small |
971 old \bl{$simp$} returns a rexp;\\ |
950 old \bl{$simp$} returns a rexp;\\ |
972 new \bl{$simp$} returns a rexp and a rectification~fun. |
951 new \bl{$simp$} returns a rexp and a rectification~function. |
973 \end{frame} |
952 \end{frame} |
974 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
953 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
975 |
954 |
976 |
955 |
977 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
956 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
982 \begin{tabular}{l} |
961 \begin{tabular}{l} |
983 \bl{$simp(r)$}:\\ |
962 \bl{$simp(r)$}:\\ |
984 \quad case \bl{$r = r_1 + r_2$}\\ |
963 \quad case \bl{$r = r_1 + r_2$}\\ |
985 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ |
964 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ |
986 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ |
965 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ |
987 \qquad case \bl{$r_{1s} = \varnothing$}: |
966 \qquad case \bl{$r_{1s} = \ZERO$}: |
988 return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\ |
967 return \bl{$(r_{2s}, \lambda v. \,Right(f_{2s}(v)))$}\\ |
989 \qquad case \bl{$r_{2s} = \varnothing$}: |
968 \qquad case \bl{$r_{2s} = \ZERO$}: |
990 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ |
969 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ |
991 \qquad case \bl{$r_{1s} = r_{2s}$}: |
970 \qquad case \bl{$r_{1s} = r_{2s}$}: |
992 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ |
971 return \bl{$(r_{1s}, \lambda v. \,Left(f_{1s}(v)))$}\\ |
993 \qquad otherwise: |
972 \qquad otherwise: |
994 return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\ |
973 return \bl{$(r_{1s} + r_{2s}, f_{alt}(f_{1s}, f_{2s}))$}\\ |
1008 |
987 |
1009 |
988 |
1010 \end{frame} |
989 \end{frame} |
1011 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
990 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1012 |
991 |
|
992 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1013 \begin{frame}[c] |
993 \begin{frame}[c] |
1014 |
994 |
1015 {\footnotesize\lstinputlisting[language=Scala,numbers=none, |
995 {\footnotesize\lstinputlisting[language=Scala,numbers=none, |
1016 xleftmargin=-5mm] {../progs/app05.scala}} |
996 xleftmargin=-5mm] {../progs/app05.scala}} |
1017 |
997 |
1018 \end{frame} |
998 \end{frame} |
|
999 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1019 |
1000 |
1020 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1001 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1021 \begin{frame}[c] |
1002 \begin{frame}[c] |
1022 \frametitle{Rectification} |
1003 \frametitle{Rectification} |
1023 |
1004 |
1025 \begin{tabular}{@{\hspace{-3mm}}l} |
1006 \begin{tabular}{@{\hspace{-3mm}}l} |
1026 \bl{$simp(r)$}:\ldots\\ |
1007 \bl{$simp(r)$}:\ldots\\ |
1027 \quad case \bl{$r = r_1 \cdot r_2$}\\ |
1008 \quad case \bl{$r = r_1 \cdot r_2$}\\ |
1028 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ |
1009 \qquad let \bl{$(r_{1s}, f_{1s}) = simp(r_1)$}\\ |
1029 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ |
1010 \qquad \phantom{let} \bl{$(r_{2s}, f_{2s}) = simp(r_2)$}\smallskip\\ |
1030 \qquad case \bl{$r_{1s} = \varnothing$}: |
1011 \qquad case \bl{$r_{1s} = \ZERO$}: |
1031 return \bl{$(\varnothing, f_{error})$}\\ |
1012 return \bl{$(\ZERO, f_{error})$}\\ |
1032 \qquad case \bl{$r_{2s} = \varnothing$}: |
1013 \qquad case \bl{$r_{2s} = \ZERO$}: |
1033 return \bl{$(\varnothing, f_{error})$}\\ |
1014 return \bl{$(\ZERO, f_{error})$}\\ |
1034 \qquad case \bl{$r_{1s} = \epsilon$}: |
1015 \qquad case \bl{$r_{1s} = \ONE$}: |
1035 return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\ |
1016 return \bl{$(r_{2s}, \lambda v. \,Seq(f_{1s}(Empty), f_{2s}(v)))$}\\ |
1036 \qquad case \bl{$r_{2s} = \epsilon$}: |
1017 \qquad case \bl{$r_{2s} = \ONE$}: |
1037 return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\ |
1018 return \bl{$(r_{1s}, \lambda v. \,Seq(f_{1s}(v), f_{2s}(Empty)))$}\\ |
1038 \qquad otherwise: |
1019 \qquad otherwise: |
1039 return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\ |
1020 return \bl{$(r_{1s} \cdot r_{2s}, f_{seq}(f_{1s}, f_{2s}))$}\\ |
1040 \end{tabular} |
1021 \end{tabular} |
1041 \end{center} |
1022 \end{center} |
1105 |
1086 |
1106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1087 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1107 \begin{frame}[c] |
1088 \begin{frame}[c] |
1108 \begin{center} |
1089 \begin{center} |
1109 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
1090 \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}} |
1110 $zeroable(\varnothing)$ & $\dn$ & $true$\\ |
1091 \bl{$zeroable(\varnothing)$} & \bl{$\dn$} & \bl{$true$}\\ |
1111 $zeroable(\epsilon)$ & $\dn$ & $f\!alse$\\ |
1092 \bl{$zeroable(\epsilon)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1112 $zeroable (c)$ & $\dn$ & $f\!alse$\\ |
1093 \bl{$zeroable(c)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1113 $zeroable (r_1 + r_2)$ & $\dn$ & $zeroable(r_1) \wedge zeroable(r_2)$ \\ |
1094 \bl{$zeroable(r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\ |
1114 $zeroable (r_1 \cdot r_2)$ & $\dn$ & $zeroable(r_1) \vee zeroable(r_2)$ \\ |
1095 \bl{$zeroable(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\ |
1115 $zeroable (r^*)$ & $\dn$ & $f\!alse$\\ |
1096 \bl{$zeroable(r^*)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\ |
1116 \end{tabular} |
1097 \end{tabular} |
1117 \end{center} |
1098 \end{center} |
1118 |
1099 |
1119 \begin{center} |
1100 \begin{center} |
1120 $zeroable(r)$ if and only if $L(r) = \varnothing$ |
1101 \bl{$zeroable(r)$} if and only if \bl{$L(r) = \{\}$} |
1121 \end{center} |
1102 \end{center} |
1122 |
1103 |
1123 |
1104 |
1124 \end{frame} |
1105 \end{frame} |
1125 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1106 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |