# HG changeset patch
# User Christian Urban <urbanc@in.tum.de>
# Date 1538570231 -3600
# Node ID 19b4dad8d2023f7dab1793072d8f82bd01da3b6f
# Parent  49053023bb7eea18d60e2684dfbb54b1431cb98b
updated

diff -r 49053023bb7e -r 19b4dad8d202 handouts/ho02.pdf
Binary file handouts/ho02.pdf has changed
diff -r 49053023bb7e -r 19b4dad8d202 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}