diff -r d5776c6018f0 -r 39b7ff2cf1bc handouts/ho02.tex --- 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?