diff -r 34f77b976b88 -r f9686b22db7e slides/slides02.tex --- a/slides/slides02.tex Tue Sep 29 21:52:52 2020 +0100 +++ b/slides/slides02.tex Sat Oct 03 00:51:47 2020 +0100 @@ -637,6 +637,118 @@ \end{frame} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + \frametitle{$der$ for $n$-times} + +Case \bl{$n = 2$} and \bl{$r \cdot r$}: + +\begin{center} + \begin{tabular}{lcl} + \bl{$der\,c\,(r\cdot r)$} & \bl{$\dn$} & \bl{if \; $nullable(r)$}\\ + & & \bl{then \; \alert<3>{$(der\,c\,r)\cdot r + der\,c\,r$}}\\ + & & \bl{else \; $(der\,c\,r)\cdot r$}\bigskip\pause\\ + my claim & & \bl{$\equiv\;$} \bl{$(der\,c\,r)\cdot r$}\\ + (in this case) + \end{tabular} +\end{center} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[t] + +We know \bl{$nullable(r)$} holds!\pause + +\begin{center} + \begin{tabular}{@{}lcl} + \bl{$(der\,c\,r)\cdot r + der\,c\,r$}\pause + & \bl{$\equiv$} & \bl{$(der\,c\,r)\cdot r + (der\,c\,r) \cdot \ONE$}\medskip\pause\\ + & \bl{$\equiv$} & \bl{$(der\,c\,r)\cdot (r + \ONE)$}\medskip\pause\\ + & \bl{$\equiv$} & \bl{$(der\,c\,r)\cdot r$}\\ + \multicolumn{3}{r}{\small(remember \bl{$r$} is nullable)} + \end{tabular} +\end{center}\pause + +\rule{13cm}{0.8mm} + +\begin{textblock}{13}(2,10) +\only<6>{% + \begin{tabular}{lcl} + \bl{$der\,c\,(r\cdot r)$} & \bl{$\dn$} & \bl{if \; $nullable(r)$}\\ + & & \bl{then \; $(der\,c\,r)\cdot r + der\,c\,r$}\\ + & & \bl{else \; $(der\,c\,r)\cdot r$} + \end{tabular}} +\only<7>{% + \begin{tabular}{lcl} + \bl{$der\,c\,(r\cdot r)$} & \bl{$\dn$} & \bl{if \; $nullable(r)$}\\ + & & \bl{then \; $(der\,c\,r)\cdot r$}\\ + & & \bl{else \; $(der\,c\,r)\cdot r$} + \end{tabular}} +\only<8>{% + \begin{tabular}{lcl} + \bl{$der\,c\,(r\cdot r)$} & \bl{$\dn$} & \bl{$(der\,c\,r)\cdot r$} + \end{tabular}} +\end{textblock} + + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{center} +\begin{tabular}{ll@{\hspace{10mm}}l} +& \bl{$r\{n\}$} & \bl{$der$}\hspace{20mm}\mbox{}\\\hline\\[-4mm] +\bl{$n = 0$} : & \bl{$\ONE$} & \bl{$\ZERO$}\\ +\bl{$n = 1$} : & \bl{$r$} & \bl{$(der\,c\,r)$}\\ +\bl{$n = 2$} : & \bl{$r\cdot r$} & \bl{$(der\,c\,r)\cdot r$}\\ +\bl{$n = 3$} : & \bl{$r\cdot r\cdot r$}& \only<1>{???}\only<2->{\bl{$(der\,c\,r)\cdot r\cdot r$}}\\ +\quad\vdots +\end{tabular} +\end{center} + +\begin{textblock}{13}(1,11) +\only<3->{% + \begin{tabular}{rcl} + \bl{$nullable(r\{n\})$} & \bl{$\dn$} & + \bl{if\; $n = 0$\; then\; $true$\; else\; $nullable(r)$}\\ + \bl{$der\,c\,(r\{n\})$} & \bl{$\dn$} & + \bl{if\; $n = 0$\; then\; $\ZERO$\; else\; $(der\,c\,r)\cdot r\{n - 1\}$} + \end{tabular}} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\begin{frame}[c] + +\begin{textblock}{13}(1.5,4) + \only<1-6>{% + \begin{tabular}{@{}lcl@{}} + \bl{$der\,c\,(r\cdot r\cdot r)$} + & \bl{$\dn$} & \bl{if $nullable(r)$}\medskip\\ + & & \only<1>{\bl{then\; $(der\,c\,r)\cdot r\cdot r + der\,c\,(r\cdot r)$}}% + \only<2>{\bl{then\; $(der\,c\,r)\cdot r\cdot r + (der\,c\,r)\cdot r$}}% + \only<3>{\bl{then\; $(der\,c\,r)\cdot (r\cdot r + r)$}}% + \only<4>{\bl{then\; $(der\,c\,r)\cdot (r\cdot (r + \ONE))$}}% + \only<5>{\bl{then\; $(der\,c\,r)\cdot (r\cdot r)$}}% + \only<6>{\bl{then\; $(der\,c\,r)\cdot r\cdot r$}}\medskip\\ + & & \bl{else\; $(der\,c\,r)\cdot r\cdot r$}\\ + \end{tabular}} + \only<7->{% + \begin{tabular}{@{}lcl@{}} + \bl{$der\,c\,(r\cdot r\cdot r)$} + & \bl{$\dn$} & \bl{$(der\,c\,r)\cdot r\cdot r$}% + \end{tabular}} +\end{textblock} + +\end{frame} +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{frame}[t] @@ -869,12 +981,12 @@ \item extends to most regular expressions, for example \bl{$\sim r$} (next slide) -\item is easy to implement in a functional language (slide after) +\item is easy to implement in a functional language \item the algorithm is already quite old; there is still work to be done to use it as a tokenizer (that is relatively new work) -\item we can prove its correctness\ldots (several slides later) +\item we can prove its correctness\ldots (another video) \end{itemize} \end{frame} @@ -889,10 +1001,9 @@ \item \bl{$L(\sim{}r) \dn UNIV - L(r)$}\medskip \item \bl{$nullable (\sim{}r) \dn not\, (nullable(r))$}\medskip \item \bl{$der\,c\,(\sim{}r) \dn \;\sim{}(der\,c\,r)$} -\end{itemize}\bigskip\pause +\end{itemize}\bigskip\bigskip\medskip\pause Used often for recognising comments: - \[ \bl{/ \cdot * \cdot (\sim{}([a\mbox{-}z]^* \cdot * \cdot / \cdot [a\mbox{-}z]^*)) \cdot * \cdot /} \]