afl-material: comparison handouts/ho02.tex

equal deleted inserted replaced

-:2be8c4c77418
+:b153c04834eb
 $(r_1 \cdot r_2)^*$ & $\equiv$ & $1 + r_1\cdot (r_2 \cdot r_1)^* \cdot r_2$\\
 \end{tabular}
 \end{center}
 \noindent
-We will not use them in our algorithm, but feel free to convince you
+We will not use them in our algorithm, but feel free to convince yourself
 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? So in general it is not a trivial problem.
 \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.
-This algorithm was introduced by Janus Brzozowski in 1964, but
+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 extendable for other regular expressions such 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).
 \subsection*{The Matching Algorithm in Scala}
 %This is not an error: it hardly takes more than half a second for
 %strings up to the length of 6500. After that we receive a
 %StackOverflow exception, but still\ldots
 For running the algorithm with our first example, the evil
-regular expression $a^?{}^{\{n\}}a^{\{n\}}$, we need to implement
+regular expression $a^?{}^{\{n\}}\cdot a^{\{n\}}$, we need to implement
 the optional regular expression and the `exactly $n$-times
 regular expression'. This can be done with the translations
 \lstinputlisting[numbers=none]{../progs/app51.scala}
 \caption{The simplification function and modified
 \texttt{ders}-function; this function now
 calls \texttt{der} first, but then simplifies
 the resulting derivative regular expressions before
 building the next derivative, see
-Line~\ref{simpline}.\label{scala2}}
+Line~24.\label{scala2}}
 \end{figure}
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 \noindent
 To recap, Python and Ruby needed approximately 30 seconds to match a
 string of 28 \texttt{a}s and the regular expression $a^{?\{n\}} \cdot
 a^{\{n\}}$.  We need a third of this time to do the same with strings
-up to 11,000 \texttt{a}s.  Similarly, Java and Python needed 30
+up to 11,000 \texttt{a}s.  Similarly, Java 8 and Python needed 30
 seconds to find out the regular expression $(a^*)^* \cdot b$ does not
-match the string of 28 \texttt{a}s. We can do the same in the same amount of time
+match the string of 28 \texttt{a}s. In Java 9 and later this has been
-for strings composed of nearly 6,000,000 \texttt{a}s:
+cranked up to 39,000 \texttt{a}s, but we can do the same in the same
+amount of time for strings composed of nearly 6,000,000 \texttt{a}s:
 \begin{center}
 \begin{tikzpicture}
 \begin{axis}[
 meets its specification. To have done so, requires a few induction
 proofs about strings and regular expressions. Following the \emph{induction
 recipes} is already a big step in actually performing these proofs.
 If you do not believe it, proofs have helped me to make sure my code
 is correct and in several instances prevented me of letting slip
 embarrassing mistakes into the `wild'.
 \end{document}
+% !TeX program = latexmk -xelatex
 %%% Local Variables:
 %%% mode: latex
 %%% TeX-master: t
 %%% End:

changeset 566	b153c04834eb
parent 550	71fc4a7a7039
child 571	499007a7bce2