--- a/handouts/ho02.tex Wed May 10 17:03:21 2017 +0100
+++ b/handouts/ho02.tex Sun May 21 00:43:02 2017 +0100
@@ -14,10 +14,10 @@
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 and Java
-(the plots on the left). The first pair of plots show the running time
+(the plots on the left). The first pair of plots shows the running time
for the regular expression $(a^*)^*\cdot b$ and strings composed of
$n$ \pcode{a}s (meaning this regular expression actually does not
-match the strings). The second pair of plots show the running time for
+match the strings). The second pair of plots shows the running time for
the regular expressions $a^?{}^{\{n\}}\cdot a^{\{n\}}$ and strings
also composed of $n$ \pcode{a}s (this time the regular expressions
match the strings). To see the substantial differences in the left
@@ -278,9 +278,9 @@
\end{center}
\noindent
-We will not use them in our algorithm, but feel free to make sure they
-hold. As an aside, there has been a lot of research about questions
-like: Can one always decide when two regular expressions are
+We will not use them in our algorithm, but feel free to convince you
+that they 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?