--- 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}