# HG changeset patch # User Christian Urban # Date 1415031478 0 # Node ID 796b9b81ac8daa55cd7b32fb9b1799c00f049bb6 # Parent 19f23c4c2167a402202ab20488904db47de340da updated diff -r 19f23c4c2167 -r 796b9b81ac8d handouts/ho02.pdf Binary file handouts/ho02.pdf has changed diff -r 19f23c4c2167 -r 796b9b81ac8d handouts/ho02.tex --- 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 diff -r 19f23c4c2167 -r 796b9b81ac8d handouts/ho03.pdf Binary file handouts/ho03.pdf has changed diff -r 19f23c4c2167 -r 796b9b81ac8d handouts/ho04.pdf Binary file handouts/ho04.pdf has changed diff -r 19f23c4c2167 -r 796b9b81ac8d handouts/ho04.tex --- a/handouts/ho04.tex Sun Nov 02 09:10:15 2014 +0000 +++ b/handouts/ho04.tex Mon Nov 03 16:17:58 2014 +0000 @@ -95,7 +95,7 @@ regular expression, say $r_1$, matches the string $abc$. We first build the three derivatives (according to $a$, $b$ and $c$). We then use $nullable$ to find out whether the resulting -regular expression can match the empty string. If yes we call +regular expression can match the empty string. If yes, we call the function $mkeps$. \begin{figure}[t] @@ -140,7 +140,7 @@ \end{tabular} \end{center} -\noindent There are no cases for $\epsilon$ and $c$, since +\noindent There are no cases for $\varnothing$ and $c$, since these regular expression cannot match the empty string. Note also that in case of alternatives we give preference to the regular expression on the left-hand side. This will become @@ -172,7 +172,7 @@ \noindent This definition is by recursion on the regular expression and by analysing the shape of the values. Therefore -there are, for example, three cases for sequnece regular +there are, for example, three cases for sequence regular expressions. The last clause for the star regular expression returns a list where the first element is $inj\,r\,c\,v$ and the other elements are $vs$. That means $\_\,::\,\_$ should be