--- a/slides/slides02.tex Sat Sep 26 23:45:40 2020 +0100
+++ b/slides/slides02.tex Sun Sep 27 09:15:32 2020 +0100
@@ -5,6 +5,13 @@
\usepackage{../langs}
\usepackage{../data}
+\usepackage{tcolorbox}
+\newtcolorbox{mybox}{colback=red!5!white,colframe=red!75!black}
+\newtcolorbox{mybox2}[1]{colback=red!5!white,colframe=red!75!black,fonttitle=\bfseries,title=#1}
+\newtcolorbox{mybox3}[1]{colback=Cyan!5!white,colframe=Cyan!75!black,fonttitle=\bfseries,title=#1}
+
+
+
\hfuzz=220pt
\lstset{language=Scala,
@@ -244,6 +251,44 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Simplification Example}
+
+%%Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
+
+\begin{center}
+\def\arraystretch{2}
+\begin{tabular}{@{}lcl}
+ \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
+ & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
+ & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
+ & \bl{$=$} & \bl{$b \cdot r$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Simplification Example}
+
+%%Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
+
+\begin{center}
+\def\arraystretch{2}
+\begin{tabular}{@{}lcl}
+ \bl{$((\ZERO \cdot b) + \ZERO) \cdot r$}
+ & \bl{$\Rightarrow$} & \bl{$((\underline{\ZERO \cdot b}) + \ZERO) \cdot r$}\\
+ & \bl{$=$} & \bl{$(\underline{\ZERO + \ZERO}) \cdot r$}\\
+ & \bl{$=$} & \bl{$\ZERO \cdot r$}\\
+ & \bl{$=$} & \bl{$\ZERO$}\\
+\end{tabular}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
@@ -377,14 +422,43 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{\mbox{The Brzozowski Algorithm}}
+\frametitle{Derivative Example}
+
+Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
\begin{center}
-\begin{tabular}{l}
-\bl{$\textit{matches}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}
+\def\arraystretch{1.5}
+\begin{tabular}{@{}lcl}
+ \bl{$\der\,a\,((a \cdot b) + b)^*$}
+ & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
+ & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
+ & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
+ & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
+ & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
+ & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
\end{tabular}
\end{center}
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{\mbox{The Brzozowski Algorithm}}
+
+%\begin{center}
+%\begin{tabular}{l}
+%\bl{$\textit{matcher}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}
+%\end{tabular}
+%\end{center}
+
+\begin{center}
+\begin{mybox3}{}
+\bl{$\textit{matcher}\,r\,s \dn \textit{nullable}(\ders\;s\;r)$}
+\end{mybox3}
+\end{center}
\end{frame}
%%%%%%%%%%%%%%%%%
@@ -431,6 +505,22 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Idea with Derivatives}
+
+Input: string \bl{$abc$} and regular expression \bl{$r$}\medskip
+
+\begin{enumerate}
+\item \bl{$der\,a\,r$}
+\item \bl{$der\,b\,(der\,a\,r)$}
+\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
+\item finally check whether the last regular expression can match the empty string
+\end{enumerate}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -776,15 +866,15 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
-\frametitle{Coursework}
+\frametitle{Coursework 1}
-\underline{Strand 1:}
+%%\underline{Strand 1:}
\begin{itemize}
-\item Submission on Friday 11 October\\accepted until Monday 14 @ 18:00\medskip
+\item Submission on Friday 16 October @ 18:00\medskip
\item source code needs to be submitted as well\medskip
\item you can re-use my Scala code from KEATS \\
- or use any programming language you like\medskip
+ and use any programming language you like\medskip
\item \small https://nms.kcl.ac.uk/christian.urban/ProgInScala2ed.pdf\normalsize
\end{itemize}
@@ -792,7 +882,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[t]
\frametitle{Proofs about Rexps}
@@ -893,7 +983,7 @@
\begin{tabular}{rp{4cm}}
\bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
\bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
-\bl{$\dn$} & \bl{$matches\,s\,r$}
+\bl{$\dn$} & \bl{$matcher\,s\,r$}
\end{tabular}
\end{center}
@@ -951,7 +1041,7 @@
We can finally prove
\begin{center}
-\bl{$matches\,s\,r$} if and only if \bl{$s \in L(r)$}
+\bl{$matcher\,s\,r$} if and only if \bl{$s \in L(r)$}
\end{center}
@@ -1042,10 +1132,10 @@
\begin{frame}[c]
\frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}}
-\bigskip
-homework (written exam 80\%)\\
-coursework (20\%; first one today)\\
-submission Fridays @ 18:00 -- accepted until Mondays
+%\bigskip
+%homework (written exam 80\%)\\
+%coursework (20\%; first one today)\\
+%submission Fridays @ 18:00 -- accepted until Mondays
\mbox{}
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -1062,7 +1152,7 @@
started with the proving part though)
\begin{center}
-\bl{$matches\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}
+\bl{$matcher\,s\,r$} \;\;if and only if \;\; \bl{$s \in L(r)$}
\end{center}\bigskip\bigskip
\small
@@ -1071,86 +1161,11 @@
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{The Derivative of a Rexp}
-
-\begin{center}
-\begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {\hspace{-10mm}}l@ {}}
- \bl{$der\, c\, (\ZERO)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
- \bl{$der\, c\, (\ONE)$} & \bl{$\dn$} & \bl{$\ZERO$} & \\
- \bl{$der\, c\, (d)$} & \bl{$\dn$} & \bl{if $c = d$ then $\ONE$ else $\ZERO$} & \\
- \bl{$der\, c\, (r_1 + r_2)$} & \bl{$\dn$} & \bl{$der\, c\, r_1 + der\, c\, r_2$} & \\
- \bl{$der\, c\, (r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{if $nullable (r_1)$}\\
- & & \bl{then $(der\,c\,r_1) \cdot r_2 + der\, c\, r_2$}\\
- & & \bl{else $(der\, c\, r_1) \cdot r_2$}\\
- \bl{$der\, c\, (r^*)$} & \bl{$\dn$} & \bl{$(der\,c\,r) \cdot (r^*)$} &\medskip\\
-
- \bl{$\textit{ders}\, []\, r$} & \bl{$\dn$} & \bl{$r$} & \\
- \bl{$\textit{ders}\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\textit{ders}\,s\,(der\,c\,r)$} & \\
- \end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Example}
-
-Given \bl{$r \dn ((a \cdot b) + b)^*$} what is
-
-\begin{center}
-\def\arraystretch{1.5}
-\begin{tabular}{@{}lcl}
- \bl{$\der\,a\,((a \cdot b) + b)^*$}
- & \bl{$\Rightarrow$}& \bl{$\der\,a\, \underline{((a \cdot b) + b)^*}$}\\
- & \bl{$=$} & \bl{$(der\,a\,(\underline{(a \cdot b) + b})) \cdot r$}\\
- & \bl{$=$} & \bl{$((der\,a\,(\underline{a \cdot b})) + (der\,a\,b)) \cdot r$}\\
- & \bl{$=$} & \bl{$(((der\,a\,\underline{a}) \cdot b) + (der\,a\,b)) \cdot r$}\\
- & \bl{$=$} & \bl{$((\ONE \cdot b) + (der\,a\,\underline{b})) \cdot r$}\\
- & \bl{$=$} & \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-Input: string \bl{$abc$} and regular expression \bl{$r$}
-
-\begin{enumerate}
-\item \bl{$der\,a\,r$}
-\item \bl{$der\,b\,(der\,a\,r)$}
-\item \bl{$der\,c\,(der\,b\,(der\,a\,r))$}\bigskip\pause
-\item finally check whether the last regular expression can match the empty string
-\end{enumerate}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Simplification}
-
-Given \bl{$r \dn ((a \cdot b) + b)^*$}, you can simplify as follows
-
-\begin{center}
-\def\arraystretch{2}
-\begin{tabular}{@{}lcl}
- \bl{$((\ONE \cdot b) + \ZERO) \cdot r$}
- & \bl{$\Rightarrow$} & \bl{$((\underline{\ONE \cdot b}) + \ZERO) \cdot r$}\\
- & \bl{$=$} & \bl{$(\underline{b + \ZERO}) \cdot r$}\\
- & \bl{$=$} & \bl{$b \cdot r$}\\
-\end{tabular}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}[c]
@@ -1230,7 +1245,7 @@
\begin{tabular}{rp{4cm}}
\bl{$\Leftrightarrow$} & \bl{$[] \in L(\ders\,s\,r)$}\medskip\\
\bl{$\Leftrightarrow$} & \bl{$nullable(\ders\,s\,r)$}\medskip\\
- \bl{$\dn$} & \bl{$matches\,s\,r$}
+ \bl{$\dn$} & \bl{$matcher\,s\,r$}
\end{tabular}
\end{center}