--- a/slides/slides04.tex Sat Oct 13 13:51:28 2018 +0100
+++ b/slides/slides04.tex Tue Oct 16 00:42:10 2018 +0100
@@ -27,28 +27,164 @@
\begin{center}
\begin{tabular}{ll}
Email: & christian.urban at kcl.ac.uk\\
- Office: & N7.07 (North Wing, Bush House)\\
- Slides: & KEATS (also home work is there)\\
+ Office: & N\liningnums{7.07} (North Wing, Bush House)\\
+ Slides: & KEATS (also homework is there)\\
\end{tabular}
\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[t]
+\frametitle{Survey: Thanks!}
+\small
+
+\hspace{9mm}{\it``\ldots Thanks a million! Thanks without end!''}
+
+\begin{textblock}{3}(12,1.7)
+\includegraphics[scale=0.1]{../pics/stickman.jpg}
+\end{textblock}\pause
+
+\begin{textblock}{6}(1,4.15)
+\begin{bubble}[6.7cm]
+ \it ``Urban is a very talented lecturer: thorough, concise,
+ clear, and cares to make sure that we are learning!''
+\end{bubble}
+\end{textblock}
+
+\only<3>{
+\begin{textblock}{6}(0.6,8.5)
+\includegraphics[scale=0.2]{../pics/s1.png}
+\end{textblock}
+\begin{textblock}{6}(8,8.5)
+\includegraphics[scale=0.2]{../pics/s2.png}
+\end{textblock}}
+
+\only<4>{
+\begin{textblock}{6}(0.6,8.5)
+\includegraphics[scale=0.2]{../pics/s3.png}
+\end{textblock}
+\begin{textblock}{6}(8,8.5)
+\includegraphics[scale=0.2]{../pics/s4.png}
+\end{textblock}}
+
+% \begin{itemize}
+% \item {\bf My Voice} ``lecturer speaks in a low voice and
+% is hard to hear him'' ``please use mic'' ``please use mic
+% \& lecture recording''
+% \item {\bf Pace} ``faster pace'' ``a bit quick for me
+% personally''
+% \item {\bf Recording} ``please use recording class''
+% \item {\bf Module Name} ``misleading''
+% \item {\bf Examples} ``more examples''
+% \item {\bf Assessment} ``really appreciate extension of
+% first coursework''
+% \end{itemize}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Regular Expressions}
-In programming languages they are often used to recognise:\medskip
+\begin{center}
+\begin{tikzpicture}[scale=2,>=stealth',very thick,
+ every state/.style={minimum size=0pt,draw=blue!50,very thick,fill=blue!20},]
+ \only<-7>{\node[state, initial] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+ \only<8->{\node[state, initial,accepting] (q0) at ( 0,1) {$\mbox{Q}_0$};}
+ \only<-7>{\node[state] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+ \only<8->{\node[state,accepting] (q1) at ( 1,1) {$\mbox{Q}_1$};}
+ \node[state] (q2) at ( 2,1) {$\mbox{Q}_2$};
+ \path[->] (q0) edge[bend left] node[above] {\alert{$a$}} (q1)
+ (q1) edge[bend left] node[above] {\alert{$b$}} (q0)
+ (q2) edge[bend left=50] node[below] {\alert{$b$}} (q0)
+ (q1) edge node[above] {\alert{$a$}} (q2)
+ (q2) edge [loop right] node {\alert{$a$}} ()
+ (q0) edge [loop below] node {\alert{$b$}} ()
+ ;
+\end{tikzpicture}
+\end{center}\bigskip
-\begin{itemize}
-\item symbols, digits
-\item identifiers
-\item numbers (non-leading zeros)
-\item keywords
-\item comments
-\end{itemize}\bigskip
+\begin{center}
+\begin{tabular}{r@ {\hspace{2mm}}c@ {\hspace{2mm}}l}
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_1\,b + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_1\,a + \mbox{Q}_2\,a$}\\
+\end{tabular}
+\end{center}
+
+
+Arden's Lemma:
+\begin{center}
+If \bl{$q = q\,r + s$}\; then\; \bl{$q = s\, r^*$}
+\end{center}
+
+\only<2-6>{\small
+\begin{textblock}{6}(1,0.8)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{substitute \bl{$\mbox{Q}_1$} into \bl{$\mbox{Q}_0$} + \bl{$\mbox{Q}_2$}:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,b + \mbox{Q}_0\,a\,b + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<3-6>{\small
+\begin{textblock}{6}(2,4.15)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{simplifying \bl{$\mbox{Q}_0$}:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a + \mbox{Q}_2\,a$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
-\mbox{}\hfill\bl{\url{http://www.regexper.com}}
+\only<4-6>{\small
+\begin{textblock}{6}(3,7.55)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+ \multicolumn{3}{@{}l}{Arden for \bl{$\mbox{Q}_2$}:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b) + \mbox{Q}_2\,b$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$\mbox{Q}_0\,a\,a\,(a^*)$}
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<5-6>{\small
+\begin{textblock}{6}(4,10.9)
+\begin{bubble}[7.5cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+ \multicolumn{3}{@{}l}{Substitute \bl{$\mbox{Q}_2$} and simplify:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$\ONE + \mbox{Q}_0\,(b + a\,b + a\,a\,(a^*)\,b)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+\only<6>{\small
+\begin{textblock}{6}(5,13.4)
+\begin{bubble}[7.5cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+ \multicolumn{3}{@{}l}{Arden again for \bl{$\mbox{Q}_0$}:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
+
+\only<7->{\small
+\begin{textblock}{6}(6,11.5)
+\begin{bubble}[6.7cm]
+\begin{tabular}{r@ {\hspace{1mm}}c@ {\hspace{1mm}}l}
+\multicolumn{3}{@{}l}{Finally:}\\
+\bl{$\mbox{Q}_0$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*$}\\
+\bl{$\mbox{Q}_1$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a$}\\
+\bl{$\mbox{Q}_2$} & \bl{$=$} & \bl{$(b + a\,b + a\,a\,(a^*)\,b)^*\,a\,a\,(a^*)$}\\
+\end{tabular}
+\end{bubble}
+\end{textblock}}
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -98,10 +234,12 @@
legend cell align=left]
\addplot[blue,mark=*, mark options={fill=white}] table {re-python.data};
\addplot[brown,mark=pentagon*, mark options={fill=white}] table {re-ruby.data};
-\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data};
+\addplot[red,mark=triangle*, mark options={fill=white}] table {nfasearch.data};
\end{axis}
\end{tikzpicture}
+The punchline is that existing libraries do depth-first search in NFAs.
+
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -261,6 +399,7 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -305,7 +444,7 @@
minimum height=18mm, minimum width=20mm,
top color=white,bottom color=black!20}]
- \node at (3.05, 1.8) {\Large\bf Write A Compiler};
+ \node at (3.05, 1.8) {\Large\bf Write a compiler};
\node (0) at (-2.3,0) {};
@@ -335,24 +474,21 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Survey: Thanks!}
-\small
+\frametitle{Regular Expressions}
+
+In programming languages they are often used to recognise:\medskip
-% \begin{itemize}
-% \item {\bf My Voice} ``lecturer speaks in a low voice and
-% is hard to hear him'' ``please use mic'' ``please use mic
-% \& lecture recording''
-% \item {\bf Pace} ``faster pace'' ``a bit quick for me
-% personally''
-% \item {\bf Recording} ``please use recording class''
-% \item {\bf Module Name} ``misleading''
-% \item {\bf Examples} ``more examples''
-% \item {\bf Assessment} ``really appreciate extension of
-% first coursework''
-% \end{itemize}
-
+\begin{itemize}
+\item symbols, digits
+\item identifiers
+\item numbers (non-leading zeros)
+\item keywords
+\item comments
+\end{itemize}\bigskip
+
+\mbox{}\hfill\bl{\url{http://www.regexper.com}}
\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -364,13 +500,13 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{?? Test Case}
-
-\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}
-
-\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%\begin{frame}[c]
+%\frametitle{?? Test Case}
+%
+%\mbox{\lstinputlisting[language=While]{../progs/collatz.while}}
+%
+%\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -444,7 +580,7 @@
There is one small problem with the tokenizer. How should we
-tokenize:
+tokenize\ldots?
\begin{center}
\large\code{"x-3"}
@@ -478,7 +614,7 @@
letters followed by ``letters + numbers + \_''$^*$
\[
-\bl{iffoo}
+\bl{if}\qquad\bl{iffoo}
\]
\end{frame}
@@ -576,8 +712,8 @@
& \bl{$\mid$} & \bl{$Seq(v_1,v_2)$}\\
& \bl{$\mid$} & \bl{$Left(v)$} \\
& \bl{$\mid$} & \bl{$Right(v)$} \\
- & \bl{$\mid$} & \bl{$[]$} \\
- & \bl{$\mid$} & \bl{$[v_1,\ldots\,v_n]$} \\
+ & \bl{$\mid$} & \bl{$Stars\,[]$} \\
+ & \bl{$\mid$} & \bl{$Stars\,[v_1,\ldots\,v_n]$} \\
\end{tabular}
\end{column}
\end{columns}
@@ -610,7 +746,7 @@
& & \bl{then $Left(mkeps(r_1))$}\\
& & \bl{else $Right(mkeps(r_2))$}\\
\bl{$mkeps\,(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),mkeps(r_2))$}\\
- \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$[]$} \\
+ \bl{$mkeps\,(r^*)$} & \bl{$\dn$} & \bl{$Stars\,[]$} \\
\end{tabular}
\end{center}
@@ -624,14 +760,14 @@
Injecting (``Adding'') a character to a value\\[-12mm]\mbox{}
\begin{center}
-\begin{tabular}{@{}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
- \bl{$inj\,(c)\,c\,Empty$} & \bl{$\dn$} & \bl{$Char\,c$}\\
- \bl{$inj\,(r_1 + r_2)\,c\,Left(v)$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
- \bl{$inj\,(r_1 + r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Seq(v_1,v_2)$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Left(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
- \bl{$inj\,(r_1 \cdot r_2)\,c\,Right(v)$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
- \bl{$inj\,(r^*)\,c\,Seq(v,vs)$} & \bl{$\dn$} & \bl{$inj\,r\,c\,v\,::\,vs$}\\
+\begin{tabular}{@{\hspace{-3mm}}l@{\hspace{1mm}}c@{\hspace{1mm}}l@{}}
+ \bl{$inj\,(c)\,c\,(Empty)$} & \bl{$\dn$} & \bl{$Char\,c$}\\
+ \bl{$inj\,(r_1 + r_2)\,c\,(Left(v))$} & \bl{$\dn$} & \bl{$Left(inj\,r_1\,c\,v)$}\\
+ \bl{$inj\,(r_1 + r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Right(inj\,r_2\,c\,v)$}\\
+ \bl{$inj\,(r_1 \cdot r_2)\,c\,(Seq(v_1,v_2))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+ \bl{$inj\,(r_1 \cdot r_2)\,c\,(Left(Seq(v_1,v_2)))$} & \bl{$\dn$} & \bl{$Seq(inj\,r_1\,c\,v_1,v_2)$}\\
+ \bl{$inj\,(r_1 \cdot r_2)\,c\,(Right(v))$} & \bl{$\dn$} & \bl{$Seq(mkeps(r_1),inj\,r_2\,c\,v)$}\\
+ \bl{$inj\,(r^*)\,c\,(Seq(v,vs))$} & \bl{$\dn$} & \bl{$Stars\,(inj\,r\,c\,v\,::\,vs)$}\\
\end{tabular}
\end{center}\bigskip
@@ -909,7 +1045,7 @@
\begin{itemize}
\item If we simplify after the derivative, then we are building the
-value for the simplified regular expression, but \emph{not} for the original
+value for the simplified regular expression, but \alert{\textbf{not}} for the original
regular expression.
\end{itemize}
@@ -956,12 +1092,13 @@
\end{center}
and answer how this regular expression matches the empty string
+ with the value
\begin{center}
\bl{$Right(Right(Empty))$}
\end{center}\bigskip
- But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$}.
+ But now we simplify this to \bl{$\ONE$} and would produce \bl{$Empty$} (see \textit{mkeps}).
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -1199,7 +1336,7 @@
\bl{$env(Left(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
\bl{$env(Right(v))$} & \bl{$\dn$} & \bl{$env(v)$}\\
\bl{$env(Seq(v_1,v_2))$}& \bl{$\dn$} & \bl{$env(v_1) \,@\, env(v_2)$}\\
- \bl{$env([v_1,\ldots ,v_n])$} & \bl{$\dn$} &
+ \bl{$env(Stars\,[v_1,\ldots ,v_n])$} & \bl{$\dn$} &
\bl{$env(v_1) \,@\ldots @\, env(v_n)$}\\
\bl{$env(Rec(x:v))$} & \bl{$\dn$} & \bl{$(x:|v|) :: env(v)$}\\
\end{tabular}
@@ -1301,8 +1438,8 @@
\begin{frame}[c]
\begin{center}
\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
-\bl{$zeroable(\varnothing)$} & \bl{$\dn$} & \bl{$true$}\\
-\bl{$zeroable(\epsilon)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
+\bl{$zeroable(\ZERO)$} & \bl{$\dn$} & \bl{$true$}\\
+\bl{$zeroable(\ONE)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
\bl{$zeroable(c)$} & \bl{$\dn$} & \bl{$\textit{false}$}\\
\bl{$zeroable(r_1 + r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \wedge zeroable(r_2)$}\\
\bl{$zeroable(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$zeroable(r_1) \vee zeroable(r_2)$}\\