diff -r 955d5b3b0619 -r 2849c305b12d handouts/ho04.tex --- a/handouts/ho04.tex Sun Oct 15 20:47:14 2017 +0100 +++ b/handouts/ho04.tex Tue Oct 17 13:49:45 2017 +0100 @@ -5,7 +5,7 @@ \begin{document} -\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016} +\fnote{\copyright{} Christian Urban, King's College London, 2014, 2015, 2016, 2017} \section*{Handout 4 (Sulzmann \& Lu Algorithm)} @@ -28,7 +28,7 @@ mathematical proof that their algorithm is really correct---the proof Sulzmann \& Lu had originally given contained major flaws. Such correctness proofs are important: Kuklewicz maintains a unit-test library -for the kind of algorithma we are interested in here and he showed +for the kind of algorithms we are interested in here and he showed that many implementations in the ``wild'' are buggy, that is not satisfy his unit tests: @@ -81,8 +81,8 @@ corresponding to the two alternatives. Note that $r^*$ is associated with a list of values, one for each copy of $r$ that was needed to match the string. This means we might also -return the empty list $Stars []$, if no copy was needed in case -of $r^*$. For sequence, there is exactly one value, composed +return the empty list $Stars []$, if no copy was needed +for $r^*$. For sequence, there is exactly one value, composed of two component values ($v_1$ and $v_2$). My implementation of regular expressions and values in Scala is @@ -381,7 +381,7 @@ $r_2$ or $r_{2s}$. Unfortunately, this is still not the right value in general because there might be some simplifications that happened inside $r_2$ and for which the simplification -function retuned also a rectification function $f_{2s}$. So in +function returned also a rectification function $f_{2s}$. So in fact we need to apply this one too which gives \begin{center} @@ -587,7 +587,7 @@ {\ifodd\value{lstnumber}\color{capri!3}\fi}]{../progs/app61.scala} \caption{The Scala code for the simplification function. The -first part defines some auxillary functions for the rectification. +first part defines some auxiliary functions for the rectification. The second part give the simplification function. \label{simprect}} \end{figure} @@ -607,7 +607,7 @@ \noindent This corresponds to the $matches$ function we have seen in earlier lectures. In the first clause we are given an -empty string, $[]$, and need to test wether the regular +empty string, $[]$, and need to test whether the regular expression is $nullable$. If yes, we can proceed normally and just return the value calculated by $\textit{mkeps}$. The second clause is for strings where the first character is $c$, say, and the