equal
deleted
inserted
replaced
342 \ldots and the point of the this lecture is to decide this problem as |
342 \ldots and the point of the this lecture is to decide this problem as |
343 fast as possible (unlike Python, Ruby, Java etc) |
343 fast as possible (unlike Python, Ruby, Java etc) |
344 |
344 |
345 \end{frame} |
345 \end{frame} |
346 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
346 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
347 |
347 |
|
348 |
348 |
349 |
349 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
350 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
350 \begin{frame}[c] |
351 \begin{frame}[c] |
351 \frametitle{\mbox{Brzozowski's Algorithm (1)}} |
352 \frametitle{\mbox{Brzozowski's Algorithm (1)}} |
352 |
353 |
1009 \] |
1010 \] |
1010 |
1011 |
1011 \end{frame} |
1012 \end{frame} |
1012 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1013 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1013 |
1014 |
1014 |
1015 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1016 \begin{frame}[c] |
|
1017 \frametitle{The Specification for Matching} |
|
1018 |
|
1019 \begin{bubble}[10cm] |
|
1020 \large |
|
1021 A regular expression \bl{$r$} matches a string~\bl{$s$} |
|
1022 provided: |
|
1023 \begin{center} |
|
1024 \bl{$s \in L(r)$} |
|
1025 \end{center}\medskip |
|
1026 \end{bubble} |
|
1027 |
|
1028 |
|
1029 \begin{center} |
|
1030 \onslide<2>{\bl{\large$\forall\,r\,s.\;$}} |
|
1031 \bl{$matcher\,s\,r$} \;if and only if\ \bl{$s \in L(r)$} |
|
1032 \end{center} |
|
1033 |
|
1034 |
|
1035 \end{frame} |
|
1036 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1037 |
|
1038 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1039 \begin{frame}[c] |
|
1040 \frametitle{nullable and \boldmath$der$} |
|
1041 |
|
1042 The central properties:\bigskip\bigskip |
|
1043 |
|
1044 \large |
|
1045 \begin{quote} |
|
1046 \onslide<3>{\bl{$\forall r.\phantom{\,c}\;$}}% |
|
1047 \bl{$nullable(r)$} \;if and only if\; \bl{$[] \in L(r)$} |
|
1048 \end{quote}\bigskip\bigskip\pause |
|
1049 |
|
1050 \begin{quote} |
|
1051 \onslide<3>{\bl{$\forall r\,c.\;$}}% |
|
1052 \bl{$L(der\,c\,r) \;=\; Der\,c\,(L(r))$} |
|
1053 \end{quote} |
|
1054 |
|
1055 \end{frame} |
|
1056 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1015 |
1057 |
1016 |
1058 |
1017 |
1059 |
1018 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1060 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1019 \begin{frame}[t] |
1061 \begin{frame}[t] |
1054 \end{frame} |
1096 \end{frame} |
1055 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1097 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1056 |
1098 |
1057 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1099 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1058 \begin{frame}[c] |
1100 \begin{frame}[c] |
1059 \frametitle{Proofs about Rexp (3)} |
1101 \frametitle{Proofs about Rexp} |
1060 |
1102 |
1061 Assume \bl{$P(r)$} is the property: |
1103 Assume \bl{$P(r)$} is the property: |
1062 |
1104 |
1063 \begin{center} |
1105 \begin{center} |
1064 \bl{$nullable(r)$} if and only if \bl{$[] \in L(r)$} |
1106 \bl{$nullable(r)$} if and only if \bl{$[] \in L(r)$} |
1065 \end{center} |
1107 \end{center} |
1066 |
1108 |
1067 \end{frame} |
1109 \end{frame} |
1068 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1110 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
|
1111 |
|
1112 \end{document} |
|
1113 % below are slides for proving. |
1069 |
1114 |
1070 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1115 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
1071 \begin{frame}[c] |
1116 \begin{frame}[c] |
1072 \frametitle{Proofs about Rexp (4)} |
1117 \frametitle{Proofs about Rexp (4)} |
1073 |
1118 |