
diff -r e7dbebf43ac3 -r d82c91f85391 slides/slides03.tex
--- a/slides/slides03.tex	Mon Sep 30 10:47:49 2024 +0100
+++ b/slides/slides03.tex	Fri Oct 11 19:13:00 2024 +0100
@@ -34,8 +34,8 @@
   \normalsize
   \begin{center}
   \begin{tabular}{ll}
-  Email:  & christian.urban at kcl.ac.uk\\
-Office Hour: & Thurdays 15 -- 16\\  
+    Email:  & christian.urban at kcl.ac.uk\\
+    Office Hour: & Friday 12 -- 14\\  
   Location: & N7.07 (North Wing, Bush House)\\
   Slides \& Progs: & KEATS\\
   Pollev: & \texttt{\alert{https://pollev.com/cfltutoratki576}}\\  
@@ -61,6 +61,94 @@
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%     
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
+{
+\setbeamercolor{background canvas}{bg=cream}
+\begin{frame}[c]
+\frametitle{For Installation Problems}
+
+\begin{itemize}
+\item Harry Dilnot (harry.dilnot@kcl.ac.uk) \\
+  \;\;Windows expert
+\item Oliver Iliffe (oliver.iliffe@kcl.ac.uk) 
+\end{itemize}
+  
+\end{frame}
+}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{mybox3}{From Pollev last week}\it    
+Is the equivalence of two regexes belong in the P or NP class of problems?
+\end{mybox3}  
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{mybox3}{From Pollev last week}\it    
+  If state machines are not efficient, then how/why do many lexer
+  packages like the logos crate in rust compile down a lexer
+  definition down to a jump table driven state machine?
+  \textcolor{gray}{Could we
+  achieve quicker lexing with things like SIMD instructions?}
+\end{mybox3}  
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\boldmath$(abcdef)^{\{n\}}$ in Rust and Scala}
+  
+\begin{textblock}{14}(1,3)
+\begin{tikzpicture}
+\begin{axis}[
+    xlabel={copies of $[abcdef]$}, 
+    x label style={at={(0.45,-0.16)}},
+    ylabel={time in secs},
+    enlargelimits=false, 
+    ytick={0,10,...,60},
+    ymax=65,
+    xmax=50000,
+    xtick={0,10000,...,40000},
+    scaled ticks=false,
+    axis lines=left,
+    width=10cm,
+    height=6cm,
+    legend entries={Rust, Scala V3},
+    legend style={font=\small,at={(1.15,0.48)},anchor=north},
+    legend cell align=left]
+    \addplot[blue,mark=*, mark options={fill=white}] table {re-rust2.data};
+    \only<2>{\addplot[red,mark=*, mark options={fill=white}] table {re-scala2.data};}
+\end{axis}
+\end{tikzpicture}
+\end{textblock}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+
+\begin{mybox3}{From Pollev last week}\it    
+  For a regular expression $r = r_1 \cdot r_2$, to prove that
+  $der\;c\;r = (der\;c\;r) \cdot r^{\{n-1\}}$, is there a
+  way to prove it in the general case instead
+  of how you do the calculations for each $n$ in the videos?
+\end{mybox3}  
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
 {
 \setbeamercolor{background canvas}{bg=cream}
 \begin{frame}<1-10>[c]
@@ -1670,7 +1758,9 @@
 % \end{center}
 
 % \end{frame}
-% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -1760,6 +1850,8 @@
 \end{frame}}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
+
+
 \begin{frame}<1-3>[c]
 \end{frame}  
 
@@ -1795,40 +1887,108 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\mbox{CW1: Regexes and \boldmath$L$-function}}
+
+Given 
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{20mm}}l@ {\hspace{2mm}}l@ {\hspace{2mm}}l}
+\bl{$r^+$}        & \bl{$L(r^+)$}         & \bl{$\dn$}  & \bl{$\bigcup_{1\le i}.\;L(r)^i$}\\
+\bl{$r^?$}        & \bl{$L(r^?)$}         & \bl{$\dn$}  & \bl{$L(r) \cup \{[]\}$}\\  
+\bl{$r_1 \,\&\, r_2$} &  \bl{$L(r_1 \& r_2)$} &  \bl{$\dn$} & \bl{$L(r_1) \cap L(r_2)$} \\
+\bl{$r^{\{n\}}$}   & \bl{$L(r^{\{n\}})$}   & \bl{$\dn$}  & \bl{$L(r)^n$}\\
+\bl{$r^{\{..m\}}$}   & \bl{$L(r^{\{..m\}})$}   & \bl{$\dn$}  & \bl{$\bigcup_{0\le i \le m}.\;L(r)^i$}\\
+\bl{$r^{\{n..\}}$}   & \bl{$L(r^{\{n..\}})$}   & \bl{$\dn$}  & \bl{$\bigcup_{n\le i}.\;L(r)^i$}\\
+\bl{$r^{\{n..m\}}$}   & \bl{$L(r^{\{n..m\}})$}   & \bl{$\dn$}  & \bl{$\bigcup_{n\le i \le m}.\;L(r)^i$}\\      
+\bl{$\sim{}r$}   & \bl{$L(\sim{}r)$}   & \bl{$\dn$}  & \bl{$\Sigma^* - L(r)$}\\      
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Nullable}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+\bl{$nullable(r^+)$}    & \bl{$\dn$} & \bl{$nullable(r)$}\\
+\bl{$nullable(r^?)$}       & \bl{$\dn$} & \bl{\textit{true}}\\
+\bl{$nullable(r_1 \,\&\, r_2)$}  & \bl{$\dn$} & \bl{$nullable(r_1) \wedge nullable(r_2)$}\\
+\bl{$nullable(r^{\{n\}})$}     & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$} \\ 
+\bl{$nullable(r^{\{..m\}})$} & \bl{$\dn$} & \bl{\textit{true}} \\
+\bl{$nullable (r^{\{n..\}})$}           & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$}\\
+\bl{$nullable (r^{\{n..m\}})$}           & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} \textit{true} \textit{else} $nullable(r)$}\\  
+\bl{$nullable (\sim{}r)$}           & \bl{$\dn$} & \bl{$!\,nullable(r)$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Derivative}
+
+\begin{center}
+\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
+\bl{$der\,c\,(r^+)$}    & \bl{$\dn$} & \bl{$(der\,c\,r)\cdot r^*$}\\
+\bl{$der\,c\,(r^?)$}       & \bl{$\dn$} & \bl{$der\,c\,r$}\\
+\bl{$der\,c\,(r_1 \,\&\, r_2)$}  & \bl{$\dn$} & \bl{$(der\,c\,r_1) \;\&\; (der\,c\,r_2)$}\\
+\bl{$der\,c\,(r^{\{n\}})$}     & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} $\ZERO$ \textit{else} $(der\,c\,r)\cdot r^{\{n - 1\}}$} \\ 
+\bl{$der\,c\,(r^{\{..m\}})$} & \bl{$\dn$} &  \bl{\textit{if} $m = 0$ \textit{then} $\ZERO$ \textit{else} $(der\,c\,r)\cdot r^{\{..m - 1\}}$}\\
+\bl{$der\,c\,(r^{\{n..\}})$}           & \bl{$\dn$} & \bl{\textit{if} $n = 0$ \textit{then} $(der\,c\,r)\cdot r^*$ \textit{else} $(der\,c\,r)\cdot r^{\{n - 1..\}}$}\\
+  \bl{$der\,c\,(r^{\{n..m\}})$}           & \bl{$\dn$} & \bl{\textit{if} $n = 0 \wedge m = 0$ \textit{then} $\ZERO$ \textit{else}}\\
+                        &            & \bl{\textit{if} $ n = 0$ \textit{then} $(der\,c\,r)\cdot r^{\{..m-1\}}$
+                                       \textit{else} $(der\,c\,r)\cdot r^{\{n-1..m-1\}}$}\\  
+\bl{$der\,c\,(\sim{}r)$}           & \bl{$\dn$} & \bl{$\sim\,(der\,c\,r)$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+
 
 \begin{frame}<1-15>[c]
 
 \end{frame}
 
-\begin{frame}[t]
-\begin{mybox3}{}
-  I always thought dfa's needed a transition for each state for each
-  character, and if not it would be an nfa not a dfa. Is there an
-  example that disproves this?
-\end{mybox3}
-\end{frame}
+% \begin{frame}[t]
+% \begin{mybox3}{}
+%   I always thought dfa's needed a transition for each state for each
+%   character, and if not it would be an nfa not a dfa. Is there an
+%   example that disproves this?
+% \end{mybox3}
+% \end{frame}
 
-\begin{frame}<1-12>[c]
-\end{frame}
+% \begin{frame}<1-12>[c]
+% \end{frame}
 
-\begin{frame}[t]
-\begin{mybox3}{}
-  Do the regular expression matchers in Python and Java 8 have more
-  features than the one implemented in this module? Or is there
-  another reason for their inefficiency?
-\end{mybox3}
-\end{frame}
+% \begin{frame}[t]
+% \begin{mybox3}{}
+%   Do the regular expression matchers in Python and Java 8 have more
+%   features than the one implemented in this module? Or is there
+%   another reason for their inefficiency?
+% \end{mybox3}
+% \end{frame}
 
 
-\begin{frame}[c]
-  \begin{itemize}
-  \item CW / censored some msgs 
-  \item power law / proof
-  \item CW feedback
-  \item too polished CW submissions
-  \item no open book  
-  \end{itemize}  
-\end{frame}
+% \begin{frame}[c]
+%   \begin{itemize}
+%   \item CW / censored some msgs 
+%   \item power law / proof
+%   \item CW feedback
+%   \item too polished CW submissions
+%   \item no open book  
+%   \end{itemize}  
+% \end{frame}
 
 
 \end{document}




