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