
diff -r 27f71d2755f0 -r 0367aa7c764b slides/slides02.tex
--- a/slides/slides02.tex	Thu Sep 26 14:19:23 2019 +0100
+++ b/slides/slides02.tex	Mon Sep 30 12:27:15 2019 +0100
@@ -1,3 +1,4 @@
+% !TEX program = xelatex
 \documentclass[dvipsnames,14pt,t]{beamer}
 \usepackage{../slides}
 \usepackage{../graphics}
@@ -34,9 +35,10 @@
   \normalsize
   \begin{center}
   \begin{tabular}{ll}
-  Email:  & christian.urban at kcl.ac.uk\\
-  Office: & N7.07 (North Wing, Bush House)\\
-  Slides: & KEATS (also homework is there)
+    Email:  & christian.urban at kcl.ac.uk\\
+    Office Hours: & Thursdays 12 -- 14\\
+    Location: & N7.07 (North Wing, Bush House)\\
+    Slides \& Progs: & KEATS (also homework is there)\\  
   \end{tabular}
   \end{center}
 
@@ -100,51 +102,73 @@
 \end{center}
 
 \small
-In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8.
+In the handouts is a similar graph for \bl{$(a^*)^* \cdot b$} and Java 8, 
+JavaScript and Python.
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Evil Regular Expressions}
-
-\begin{itemize}
-\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip
-\item Evil regular expressions\medskip
-\begin{itemize}
-\item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}
-\item \bl{$(a^*)^*$}
-\item \bl{$([a$\,-\,$z]^+)^*$}
-\item \bl{$(a + a \cdot a)^*$}
-\item \bl{$(a + a^?)^*$}
-\end{itemize}
-
-\item sometimes also called \alert{catastrophic backtracking}\bigskip
-\item \small\ldots I hope you have watched the video by the
-  StackExchange engineer  
-\end{itemize}
-
-\end{frame}
+%\begin{frame}[c]
+%\frametitle{Evil Regular Expressions}
+%
+%\begin{itemize}
+%\item \alert{R}egular \alert{e}xpression \alert{D}enial \alert{o}f \alert{S}ervice (ReDoS)\bigskip
+%\item Evil regular expressions\medskip
+%\begin{itemize}
+%\item \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}
+%\item \bl{$(a^*)^*$}
+%\item \bl{$([a$\,-\,$z]^+)^*$}
+%\item \bl{$(a + a \cdot a)^*$}
+%\item \bl{$(a + a^?)^*$}
+%\end{itemize}
+%
+%\item sometimes also called \alert{catastrophic backtracking}\bigskip
+%\item \small\ldots I hope you have watched the video by the
+%  StackExchange engineer  
+%\end{itemize}
+%
+%\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Languages}
+\frametitle{(Basic) Regular Expressions}
+
+Their inductive definition:
+
+\begin{center}
+  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
+  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\
+         & \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\
+         & \bl{$\mid$} & \bl{$c$}                         & character\\
+         & \bl{$\mid$} & \bl{$r_1 + r_2$}  & alternative / choice\\
+         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$} & sequence\\
+         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\
+  \end{tabular}
+\end{center}
+\vspace{\fill}
+
+Q: \;What about \;\bl{$r \cdot 0$} \; ?
+\end{frame}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Languages (Sets of Strings)}
 
 \begin{itemize}
 
 \item A \alert{\bf Language} is a set of strings, for example\medskip
 \begin{center}
-\bl{$\{[], hello, \textit{foobar}, a, abc\}$}
+\bl{$\{[], hello, foobar, a, abc\}$}
 \end{center}\bigskip
 
-\item \alert{\bf Concatenation} of strings and languages
+\item \alert{\bf Concatenation} for strings and languages
 
 \begin{center}
 \begin{tabular}{rcl}
-\bl{$\textit{foo}\;@\;bar$} & \bl{$=$} & \bl{$\textit{foobar}$}\medskip\\
-\bl{$A\;@\;B$} & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
+\bl{$foo\;@\;bar$} & \bl{$=$} & \bl{$foobar$}\medskip\\
+\bl{$A\;@\;B$}     & \bl{$\dn$} & \bl{$\{ s_1\,@\,s_2 \;\mid\; s_1 \in A \wedge s_2 \in B\}$}
 \end{tabular}
 \end{center}
 \bigskip
@@ -157,9 +181,53 @@
 \]
 
 \end{itemize}  
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+  \frametitle{Two Corner Cases}
+   
+  \Large
+  \begin{center}
+  \bl{$A \,@\, \{[]\} = \;?$}\bigskip\bigskip\pause\\
+  \bl{$A \,@\, \{\} = \;?$}
+  \end{center}  
+    
+  \end{frame}
+  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+  
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{
+    The Meaning of a\\[-2mm] 
+    Regular Expression}
+
+ ...all the strings a regular expression can match.   
+
+\begin{center}
+ \begin{tabular}{rcl}
+ \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
+ \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
+ \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
+ \bl{$L(r_1 + r_2)$}    & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
+ \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
+ \bl{$L(r^*)$}           & \bl{$\dn$} & \\
+  \end{tabular}
+\end{center}
+
+\begin{textblock}{14}(1.5,13.5)\small
+\bl{$L$} is a function from regular expressions to 
+sets of strings (languages):\smallskip\\
+\bl{\quad$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
+\end{textblock}
 
 \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+  
+
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -192,26 +260,23 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Homework Question}
-
-\begin{itemize}
-\item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip
-
-\begin{center}
-How many strings are in \bl{$A^4$}?
-\end{center}\bigskip\medskip\pause
-
-
-\begin{center}
-\begin{tabular}{l}
-What if \bl{$A = \{[a],[b],[c],[]\}$};\\ 
-how many strings are then in \bl{$A^4$}?
-\end{tabular}
-\end{center}
-\end{itemize}  
-
+  \frametitle{Homework Question}
+  
+  \begin{itemize}
+  \item Say \bl{$A = \{[a],[b],[c],[d]\}$}.\bigskip
+  
+  \item[]
+  How many strings are in \bl{$A^4$}\,?
+  \bigskip\medskip\pause
+  
+  
+ \item[]
+  What if \bl{$A = \{[a],[b],[c],[]\}$};\\ 
+  how many strings are then in \bl{$A^4$}\,?
+  \end{itemize}  
+  
 \end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
@@ -252,26 +317,124 @@
     The Meaning of a\\[-2mm] 
     Regular Expression}
 
-\begin{textblock}{15}(1,4)
+...all the strings a regular expression can match.   
+
+\begin{center}
  \begin{tabular}{rcl}
  \bl{$L(\ZERO)$}  & \bl{$\dn$} & \bl{$\{\}$}\\
  \bl{$L(\ONE)$}     & \bl{$\dn$} & \bl{$\{[]\}$}\\
  \bl{$L(c)$}            & \bl{$\dn$} & \bl{$\{[c]\}$}\\
  \bl{$L(r_1 + r_2)$}    & \bl{$\dn$} & \bl{$L(r_1) \cup L(r_2)$}\\
- \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$\{ s_1 \,@\, s_2 \;|\; s_1 \in L(r_1) \wedge s_2 \in L(r_2) \}$}\\
+ \bl{$L(r_1 \cdot r_2)$} & \bl{$\dn$} & \bl{$L(r_1) \,@\, L(r_2)$}\\
  \bl{$L(r^*)$}           & \bl{$\dn$} & \bl{$(L(r))\star \quad\dn \bigcup_{0 \le n} L(r)^n$}\\
   \end{tabular}
-\end{textblock}
+\end{center}
 
-\begin{textblock}{9}(6,12)\small
-\bl{$L$} is a function from regular expressions to 
-sets of strings (languages):\smallskip\\
-\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
-\end{textblock}
+%\begin{textblock}{9}(6,12)\small
+%\bl{$L$} is a function from regular expressions to 
+%sets of strings (languages):\smallskip\\
+%\bl{$L$ : Rexp $\Rightarrow$ Set$[$String$]$}
+%\end{textblock}
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+  \frametitle{
+   When Are Two Regular\\[-1mm]
+   Expressions Equivalent?}
+  
+   \begin{bubble}[10cm]
+    \large
+    Two regular expressions \bl{$r_1$} and \bl{$r_2$} are equivalent 
+    provided:\medskip 
+    \begin{center}
+      \bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$}  
+    \end{center}\medskip
+    \end{bubble}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+  
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Some Concrete Equivalences}
+
+\begin{center}
+\bl{\begin{tabular}{rcl}
+$(a + b)  + c$ & $\equiv$ & $a + (b + c)$\\
+$a + a$        & $\equiv$ & $a$\\
+$a + b$        & $\equiv$ & $b + a$\\
+$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\
+$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause
+$a \cdot a$       & $\not\equiv$ & $a$\\
+$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Some Corner Cases}
+
+\begin{center}
+\bl{\begin{tabular}{rcl}
+$a \cdot \ZERO$ & $\not\equiv$ & $a$\\
+$a + \ONE$ & $\not\equiv$ & $a$\\
+$\ONE$ & $\equiv$ & $\ZERO^*$\\
+$\ONE^*$ & $\equiv$ & $\ONE$\\
+$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\
+\end{tabular}}
+\end{center}
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
+  
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{Some Simplification Rules}
+ 
+\begin{center}
+\bl{\begin{tabular}{rcl}
+$r + \ZERO$  & $\equiv$ & $r$\\
+$\ZERO + r$  & $\equiv$ & $r$\\
+$r \cdot \ONE$ & $\equiv$ & $r$\\
+$\ONE \cdot r$     & $\equiv$ & $r$\\
+$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\
+$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\
+$r + r$ & $\equiv$ & $r$
+\end{tabular}}
+\end{center}
+ 
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+  
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+\frametitle{The Specification for Matching}
+
+\begin{bubble}[10cm]
+\large
+A regular expression \bl{$r$} matches a string~\bl{$s$} 
+provided:
+\begin{center}
+\bl{$s \in L(r)$} 
+\end{center}\medskip
+\end{bubble}
+
+\bigskip\bigskip
+
+\ldots and the point of the this lecture is to decide this problem as
+fast as possible (unlike Python, Ruby, Java etc)
+
+\end{frame}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+  
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
 \frametitle{\begin{tabular}{c}\\[3cm]\huge\alert{Questions?}\end{tabular}}
@@ -289,8 +452,6 @@
 \begin{frame}[t]
 \frametitle{Semantic Derivative\\[5mm]}
 
-  
-
 \begin{itemize}
 \item The \alert{\bf Semantic Derivative} of a 
 \underline{language}\\ w.r.t.~to a character \bl{$c$}:
@@ -308,7 +469,7 @@
 $\Der\,b\,A$ & $=$ &  $\{\mathit{ar}\}$\\  
 $\Der\,a\,A$ & $=$ & $\{\}$\pause
 \end{tabular}}
-\end{center}
+\end{center}\medskip
 
 
 We can extend this definition to strings
@@ -324,143 +485,6 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{The Specification for Matching}
-
-\begin{bubble}[10cm]
-\large
-A regular expression \bl{$r$} matches a string~\bl{$s$} 
-provided
-\begin{center}
-\bl{$s \in L(r)$} 
-\end{center}
-\end{bubble}
-
-\bigskip\bigskip
-
-\ldots and the point of the this lecture is to decide this problem as
-fast as possible (unlike Python, Ruby, Java etc)
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Regular Expressions}
-
-Their inductive definition:
-
-
-\begin{textblock}{6}(2,7.5)
-  \begin{tabular}{@ {}rrl@ {\hspace{13mm}}l}
-  \bl{$r$} & \bl{$::=$}  & \bl{$\ZERO$}  & nothing\\
-         & \bl{$\mid$} & \bl{$\ONE$}       & empty string / \pcode{""} / $[]$\\
-         & \bl{$\mid$} & \bl{$c$}              & single character\\
-         & \bl{$\mid$} & \bl{$r_1 \cdot r_2$}  & sequence\\
-         & \bl{$\mid$} & \bl{$r_1 + r_2$}      & alternative / choice\\
-         & \bl{$\mid$} & \bl{$r^*$}            & star (zero or more)\\
-  \end{tabular}
-\end{textblock}
-  
-\only<2->{\footnotesize
-\begin{textblock}{9}(2,0.5)
-\begin{bubble}[9.8cm]
-\lstinputlisting{../progs/app01.scala}
-\end{bubble}
-\end{textblock}}  
-  
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{
- When Are Two Regular\\[-1mm]
- Expressions Equivalent?}
-
-\large
-\begin{center}
-\bl{$r_1 \equiv r_2 \;\;\dn\;\; L(r_1) = L(r_2)$}
-\end{center}  
-  
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Concrete Equivalences}
-
-\begin{center}
-\bl{\begin{tabular}{rcl}
-$(a + b)  + c$ & $\equiv$ & $a + (b + c)$\\
-$a + a$        & $\equiv$ & $a$\\
-$a + b$        & $\equiv$ & $b + a$\\
-$(a \cdot b) \cdot c$ & $\equiv$ & $a \cdot (b \cdot c)$\\
-$c \cdot (a + b)$ & $\equiv$ & $(c \cdot a) + (c \cdot b)$\bigskip\bigskip\\\pause
-$a \cdot a$       & $\not\equiv$ & $a$\\
-$a + (b \cdot c)$ & $\not\equiv$ & $(a + b) \cdot (a + c)$\\
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Corner Cases}
-
-\begin{center}
-\bl{\begin{tabular}{rcl}
-$a \cdot \ZERO$ & $\not\equiv$ & $a$\\
-$a + \ONE$ & $\not\equiv$ & $a$\\
-$\ONE$ & $\equiv$ & $\ZERO^*$\\
-$\ONE^*$ & $\equiv$ & $\ONE$\\
-$\ZERO^*$ & $\not\equiv$ & $\ZERO$\\
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[t]
-\frametitle{Simplification Rules}
- 
-\begin{center}
-\bl{\begin{tabular}{rcl}
-$r + \ZERO$  & $\equiv$ & $r$\\
-$\ZERO + r$  & $\equiv$ & $r$\\
-$r \cdot \ONE$ & $\equiv$ & $r$\\
-$\ONE \cdot r$     & $\equiv$ & $r$\\
-$r \cdot \ZERO$ & $\equiv$ & $\ZERO$\\
-$\ZERO \cdot r$ & $\equiv$ & $\ZERO$\\
-$r + r$ & $\equiv$ & $r$
-\end{tabular}}
-\end{center}
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
-\frametitle{Another Homework Question}
-
-\begin{itemize}
-\item How many basic regular expressions are there to match
-  the string \bl{$abcd$}\,?\pause
-\item How many if they cannot include
-  \bl{$\ONE$} and \bl{$\ZERO$}\/?\pause
-\item How many if they are also not
-  allowed to contain stars?\pause
-\item How many if they are also
-      not allowed to contain \bl{$\_ + \_$}\/? 
-\end{itemize}  
-
-\end{frame}
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\begin{frame}[c]
 \frametitle{\mbox{Brzozowski's Algorithm (1)}}
 
 
@@ -506,7 +530,7 @@
   \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^*)$} &\bigskip\\\pause
+  \bl{$\der\, c\, (r^*)$}  & \bl{$\dn$} & \bl{$(\der\,c\,r) \cdot (r^*)$} &\medskip\bigskip\\\pause
 
   \bl{$\ders\, []\, r$}     & \bl{$\dn$} & \bl{$r$} & \\
   \bl{$\ders\, (c\!::\!s)\, r$} & \bl{$\dn$} & \bl{$\ders\,s\,(\der\,c\,r)$} & \\
@@ -592,7 +616,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Oops\ldots \;\bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
+\frametitle{Oops\ldots \boldmath\;$a^{?\{n\}} \cdot a^{\{n\}}$}
 
 \begin{center}
 \begin{tikzpicture}
@@ -672,7 +696,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{Brzozowski: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
+\frametitle{Brzozowski: \boldmath$a^{?\{n\}} \cdot a^{\{n\}}$}
 
 \begin{center}
 \begin{tikzpicture}
@@ -756,7 +780,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[t]
-\frametitle{Brzozowski: \bl{$a^{?\{n\}} \cdot a^{\{n\}}$}}
+\frametitle{Brzozowski: \boldmath$a^{?\{n\}} \cdot a^{\{n\}}$}
 
 \begin{center}
 \begin{tikzpicture}
@@ -789,9 +813,10 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
   \frametitle{
-    Another Example\\[-1mm]
-    in Java \liningnums{8} and Python}
+    Another Example\\[-2mm]
+    in Java 8, Python and JavaScript}
 
+\bigskip    
 \begin{center}
 \begin{tikzpicture}
   \begin{axis}[
@@ -806,12 +831,13 @@
     scaled ticks=false,
     axis lines=left,
     width=9cm,
-    height=5cm, 
-    legend entries={Java 8, Python},  
+    height=5.5cm, 
+    legend entries={Java 8, Python, JavaScript},  
     legend pos=north west,
     legend cell align=left]
 \addplot[blue,mark=*, mark options={fill=white}] table {re-python2.data};
 \addplot[cyan,mark=*, mark options={fill=white}] table {re-java.data};
+\addplot[red,mark=*, mark options={fill=white}] table {re-js.data};
 \end{axis}
 \end{tikzpicture}
 \end{center}
@@ -825,7 +851,7 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{Same Example in Java \liningnums{9}+}
+\frametitle{Same Example in Java 9+}
 
 \begin{center}
 \begin{tikzpicture}
@@ -905,7 +931,7 @@
 \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
+\item we can prove its correctness\ldots (several slides later)
 \end{itemize}
 
 \end{frame}
@@ -939,7 +965,7 @@
 \underline{Strand 1:}
 
 \begin{itemize}
-\item Submission on Friday 12 October\\accepted until Monday 15 @ 18:00\medskip
+\item Submission on Friday 11 October\\accepted until Monday 14 @ 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
@@ -1031,8 +1057,8 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \begin{frame}[c]
-\frametitle{\begin{tabular}{c}
-  Correctness Proof\\[-1mm] for our Matcher\end{tabular}}
+\frametitle{Correctness Proof \\[-1mm]
+            for our Matcher}
 
 \begin{itemize}
 \item We started from
@@ -1042,10 +1068,10 @@
   & \bl{$s \in L(r)$}\medskip\\
 \bl{$\Leftrightarrow$} & \bl{$[] \in \Ders\,s\,(L(r))$}\pause  
 \end{tabular}
-\end{center}
+\end{center}\bigskip
 
 \item if we can show \bl{$\Ders\, s\,(L(r)) = L(\ders\,s\,r)$} we 
-have
+have\bigskip
 
 \begin{center}
 \begin{tabular}{rp{4cm}}
@@ -1177,6 +1203,25 @@
 
 \end{frame}
 
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\begin{frame}[c]
+  \frametitle{Another Homework Question}
+  
+  \begin{itemize}
+  \item How many basic regular expressions are there to match
+    the string \bl{$abcd$}\,?\pause
+  \item How many if they cannot include
+    \bl{$\ONE$} and \bl{$\ZERO$}\/?\pause
+  \item How many if they are also not
+    allowed to contain stars?\pause
+  \item How many if they are also
+        not allowed to contain \bl{$\_ + \_$}\/? 
+  \end{itemize}  
+  
+  \end{frame}
+  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%   
+      
+
 \end{document}
 
 %%% Local Variables:  




