--- a/handouts/ho02.tex Sun Nov 02 09:10:15 2014 +0000
+++ b/handouts/ho02.tex Mon Nov 03 16:17:58 2014 +0000
@@ -149,7 +149,7 @@
\end{center}
\noindent which always hold no matter what the regular
-expression $r$ looks like. The first are easy to verify since
+expression $r$ looks like. The first two are easy to verify since
$L(\varnothing)$ is the empty set. The next two are also easy
to verify since $L(\epsilon) = \{[]\}$ and appending the empty
string to every string of another set, leaves the set
@@ -159,7 +159,6 @@
the empty set. Check the definition of \pcode{_ @ _}.
The last equivalence is again trivial.
-
What will be important later on is that we can orient these
equivalences and read them from left to right. In this way we
can view them as \emph{simplification rules}. Suppose for
@@ -172,7 +171,7 @@
\noindent If we can find an equivalent regular expression that
is simpler (smaller for example), then this might potentially
-make our matching algorithm is faster. The reason is that
+make our matching algorithm run faster. The reason is that
whether a string $s$ is in $L(r)$ or in $L(r')$ with $r\equiv r'$
will always give the same answer. In the example above you
will see that the regular expression is equivalent to $r_1$
@@ -191,7 +190,7 @@
\end{tabular}
\end{center}
-\noindent In each step I underlined where a simplification
+\noindent In each step, I underlined where a simplification
rule is applied. Our matching algorithm in the next section
will often generate such ``useless'' $\epsilon$s and
$\varnothing$s, therefore simplifying them away will make the
@@ -392,9 +391,9 @@
Another attraction of the algorithm is that it can be easily
implemented in a functional programming language, like Scala.
-Given the implementation of regular expressions in Scala given
-in the first lecture and handout, the functions for
-\pcode{matches} are shown in Figure~\ref{scala1}.
+Given the implementation of regular expressions in Scala shown
+in the first lecture and handout, the functions and subfunctions
+for \pcode{matches} are shown in Figure~\ref{scala1}.
\begin{figure}[p]
\lstinputlisting{../progs/app5.scala}
@@ -522,7 +521,7 @@
\noindent I leave it to you to contemplate whether such a
simplification can have any impact on the correctness of our
algorithm (will it change any answers?). Figure~\ref{scala2}
-give a simplification function that recursively traverses a
+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