diff -r 357c395ae838 -r e74c696821a2 handouts/ho04.tex --- a/handouts/ho04.tex Tue Aug 23 15:38:20 2016 +0200 +++ b/handouts/ho04.tex Tue Aug 23 23:12:55 2016 +0200 @@ -25,17 +25,11 @@ student and I found several rather annoying typos in their examples and definitions.} In order to give an answer for \emph{how} a regular expression matches a string, Sulzmann and -Lu introduce \emph{values}. A value will be the output of the +Lu use \emph{values}. A value will be the output of the algorithm whenever the regular expression matches the string. If the string does not match the string, an error will be -raised. Since the first phase of the algorithm by Sulzmann \& -Lu is identical to the derivative based matcher from the first -coursework, the function \textit{nullable} will be used to -decide whether as string is matched by a regular expression. -If \textit{nullable} says yes, then values are constructed -that reflect how the regular expression matched the string. - -The definitions for values is given below. They are shown +raised. +The definition for values is given below. They are shown together with the regular expressions $r$ to which they correspond: @@ -60,13 +54,12 @@ & $\mid$ & $Seq(v_1,v_2)$\\ & $\mid$ & $\Left(v)$ \\ & $\mid$ & $Right(v)$ \\ - & $\mid$ & $[v_1,\ldots\,v_n]$ \\ + & $\mid$ & $Stars [v_1,\ldots\,v_n]$ \\ \end{tabular} \end{tabular} \end{center} -\noindent The reason is that there is a very strong -correspondence between them. There is no value for the +\noindent There is no value for the $\ZERO$ regular expression, since it does not match any string. Otherwise there is exactly one value corresponding to each regular expression with the exception of $r_1 + r_2$ @@ -74,7 +67,7 @@ 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 $[]$, if no copy was needed in case +return the empty list $Stars []$, if no copy was needed in case of $r^*$. For sequence, there is exactly one value, composed of two component values ($v_1$ and $v_2$).