diff -r 12a8f57f68ea -r fdbc7d0ec04f slides/slides02.tex --- a/slides/slides02.tex Tue Sep 26 14:38:45 2017 +0100 +++ b/slides/slides02.tex Wed Sep 27 14:46:20 2017 +0100 @@ -223,6 +223,52 @@ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] +\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] + Regular Expression\end{tabular}} + +\begin{textblock}{15}(1,4) + \begin{tabular}{rcl} + \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ + \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ + \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ + \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ + \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\ + \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\ + \end{tabular} +\end{textblock} + +\begin{textblock}{6}(9,12)\small +\bl{$L$} is a function from regular expressions to +sets of strings\\ +\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] +\frametitle{\begin{tabular}{c}The Specification\\ of Matching\end{tabular}} + +\begin{bubble}[10cm] +\large +A regular expression \bl{$r$} matches a string~\bl{$s$} +provided + +\begin{center} +\bl{$s \in L(r)$}\\ +\end{center} +\end{bubble}\bigskip\bigskip + +\ldots and the point of the this lecture is +to decide this problem as fast as possible +(unlike Python, Ruby, Java etc) + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] \frametitle{Semantic Derivative} \begin{itemize} @@ -283,42 +329,6 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] -\frametitle{\begin{tabular}{c}The Meaning of a\\[-2mm] Regular Expression\end{tabular}} - -\begin{textblock}{15}(1,4) - \begin{tabular}{@ {}rcl} - \bl{$L(\ZERO)$} & \bl{$\dn$} & \bl{$\{\}$}\\ - \bl{$L(\ONE)$} & \bl{$\dn$} & \bl{$\{[]\}$}\\ - \bl{$L(c)$} & \bl{$\dn$} & \bl{$\{[c]\}$}\\ - \bl{$L(r_1 + r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\ - \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\ - \bl{$L(r^*)$} & \bl{$\dn$} & \bl{$(L(r))\star$}\\ - \end{tabular} -\end{textblock} - -\begin{textblock}{6}(9,12)\small -\bl{$L$} is a function from regular expressions to -sets of strings\\ -\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$} -\end{textblock} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% -\begin{frame}[c] - -\large -\begin{center} -What is \bl{$L(a^*)$}? -\end{center} - -\end{frame} -%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% - %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[c] \frametitle{\begin{tabular}{c}