handouts/ho02.tex
changeset 296 796b9b81ac8d
parent 291 201c2c6d8696
child 318 7975e4f0d4de
--- 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