# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1538570231 -3600
# Node ID 499007a7bce20729b3cf424d5a353656a3e6c26a
# Parent  617c3b0e0a81b73185eee4d5f9411026e8d2ca96
updated

diff -r 617c3b0e0a81 -r 499007a7bce2 handouts/ho02.pdf
Binary file handouts/ho02.pdf has changed
diff -r 617c3b0e0a81 -r 499007a7bce2 handouts/ho02.tex
--- a/handouts/ho02.tex	Mon Oct 01 23:55:53 2018 +0100
+++ b/handouts/ho02.tex	Wed Oct 03 13:37:11 2018 +0100
@@ -6,7 +6,7 @@
 
 
 \begin{document}
-\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017}
+\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017, 2018}
 
 
 \section*{Handout 2 (Regular Expression Matching)}
@@ -444,7 +444,7 @@
 language we started with.
 
 Our matching algorithm using $\textit{der}$ and $\textit{nullable}$ works
-similarly, just using regular expression instead of sets. In order to
+similarly, just using regular expressions instead of sets. In order to
 define our algorithm we need to extend the notion of derivatives from single
 characters to strings. This can be done using the following
 function, taking a string and a regular expression as input and
@@ -463,14 +463,14 @@
 algorithm:
 
 \[
-\textit{matches}\,s\,r \dn \textit{nullable}(\textit{ders}\,s\,r)
+\textit{matches}\,r\,s \dn \textit{nullable}(\textit{ders}\,s\,r)
 \]
 
 \noindent
 and we can claim that
 
 \[
-\textit{matches}\,s\,r\quad\text{if and only if}\quad s\in L(r)
+\textit{matches}\,r\,s\quad\text{if and only if}\quad s\in L(r)
 \]
 
 \noindent holds, which means our algorithm satisfies the
@@ -679,9 +679,8 @@
 (will it change any answers?). Figure~\ref{scala2} gives a
 simplification function that recursively traverses a regular
 expression and simplifies it according to the rules given at the
-beginning. There are only rules for $+$, $\cdot$ and $n$-times (the
-latter because we added it in the second version of our
-matcher). There is no simplification rule for a star, because
+beginning. There are only rules for $+$ and $\cdot$. There is 
+no simplification rule for a star, because
 empirical data and also a little thought showed that simplifying under
 a star is a waste of computation time. The simplification function
 will be called after every derivation.  This additional step removes
@@ -733,7 +732,8 @@
 seconds to find out the regular expression $(a^*)^* \cdot b$ does not
 match the string of 28 \texttt{a}s. In Java 9 and later this has been 
 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:
+amount of time for strings composed of nearly 6,000,000 \texttt{a}s. 
+This is shown in the following plot.
 
 
 \begin{center}