--- a/handouts/ho02.tex Tue Aug 31 11:49:09 2021 +0100
+++ b/handouts/ho02.tex Fri Sep 03 23:53:31 2021 +0100
@@ -8,7 +8,7 @@
\begin{document}
\fnote{\copyright{} Christian Urban, King's College London,
- 2014, 2015, 2016, 2017, 2018, 2019, 2020}
+ 2014, 2015, 2016, 2017, 2018, 2019, 2020, 2021}
\section*{Handout 2 (Regular Expression Matching)}
@@ -27,10 +27,13 @@
This lecture is about implementing a more efficient regular expression
matcher (the plots on the right below)---more efficient than the
matchers from regular expression libraries in Ruby, Python, JavaScript
-and Java (the plots on the left). For this consider some experimental
-data: The first pair of plots shows the running time for the
-regular expression $(a^*)^*\cdot b$ and strings composed of $n$
-\pcode{a}s, like
+and Java (the plots on the left).\footnote{Have a look at KEATS: students
+last year contributed also date for the Swift and Dart languages.}\medskip
+
+\noindent
+To start with let us look more closely at the experimental data: The
+first pair of plots shows the running time for the regular expression
+$(a^*)^*\cdot b$ and strings composed of $n$ \pcode{a}s, like
\[
\underbrace{\pcode{a}\ldots\pcode{a}}_{n}
\]
@@ -147,7 +150,7 @@
In what follows we will use these regular expressions and strings as
running examples. There will be several versions (V1, V2, V3,\ldots)
of our matcher.\footnote{The corresponding files are
- \texttt{re1.scala}, \texttt{re2.scala} and so on. As usual, you can
+ \texttt{re1.sc}, \texttt{re2.sc} and so on. As usual, you can
find the code on KEATS.}
Having specified in the previous lecture what
@@ -302,7 +305,9 @@
yourself that they actually hold. As an aside, there has been a lot of
research about questions like: Can one always decide when two regular
expressions are equivalent or not? What does an algorithm look like to
-decide this efficiently? So in general it is not a trivial problem.
+decide this efficiently? Surprisingly, many of such questions
+turn out to be non-trivial problems.
+
\subsection*{The Matching Algorithm}
@@ -492,15 +497,14 @@
\noindent holds, which means our algorithm satisfies the
specification. Of course we can claim many things\ldots
-whether the claim holds any water is a different question,
-which for example is the point of the Strand-2 Coursework.
+whether the claim holds any water is a different question.
This algorithm was introduced by Janusz Brzozowski in 1964, but
is more widely known only in the last 10 or so years. Its
main attractions are simplicity and being fast, as well as
being easily extendible for other regular expressions such as
$r^{\{n\}}$, $r^?$, $\sim{}r$ and so on (this is subject of
-Strand-1 Coursework 1).
+Coursework 1).
\subsection*{The Matching Algorithm in Scala}