diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw04.tex --- a/hws/hw04.tex Wed Apr 06 12:18:54 2016 +0100 +++ b/hws/hw04.tex Wed Apr 06 15:55:01 2016 +0100 @@ -33,8 +33,8 @@ \begin{center} \begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l} - $rev(\varnothing)$ & $\dn$ & $\varnothing$\\ - $rev(\epsilon)$ & $\dn$ & $\epsilon$\\ + $rev(\ZERO)$ & $\dn$ & $\ZERO$\\ + $rev(\ONE)$ & $\dn$ & $\ONE$\\ $rev(c)$ & $\dn$ & $c$\\ $rev(r_1 + r_2)$ & $\dn$ & $rev(r_1) + rev(r_2)$\\ $rev(r_1 \cdot r_2)$ & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\ @@ -56,44 +56,47 @@ holds. -\item Assume the delimiters for comments are \texttt{$\slash$*} and - \texttt{*$\slash$}. Give a regular expression that can recognise - comments of the form +\item Assume the delimiters for comments are + \texttt{$\slash$*} and \texttt{*$\slash$}. Give a + regular expression that can recognise comments of the + form \begin{center} \texttt{$\slash$*~\ldots{}~*$\slash$} \end{center} - where the three dots stand for arbitrary characters, but not comment delimiters. - (Hint: You can assume you are already given a regular expression written \texttt{ALL}, - that can recognise any character, and a regular expression \texttt{NOT} that recognises - the complement of a regular expression.) + where the three dots stand for arbitrary characters, but + not comment delimiters. (Hint: You can assume you are + already given a regular expression written \texttt{ALL}, + that can recognise any character, and a regular + expression \texttt{NOT} that recognises the complement + of a regular expression.) \item Simplify the regular expression \[ -(\varnothing \cdot (b \cdot c)) + -((\varnothing \cdot c) + \epsilon) +(\ZERO \cdot (b \cdot c)) + +((\ZERO \cdot c) + \ONE) \] -Does simplification always preserve the meaning of a regular -expression? + Does simplification always preserve the meaning of a + regular expression? -\item The Sulzmann \& Lu algorithm contains the function $mkeps$ - which answers how a regular expression can match the - empty string. What is the answer of $mkeps$ for the +\item The Sulzmann \& Lu algorithm contains the function + $mkeps$ which answers how a regular expression can match + the empty string. What is the answer of $mkeps$ for the regular expressions: \[ \begin{array}{l} - (\varnothing \cdot (b \cdot c)) + - ((\varnothing \cdot c) + \epsilon)\\ - (a + \varepsilon) \cdot (\varepsilon + \varepsilon) + (\ZERO \cdot (b \cdot c)) + + ((\ZERO \cdot c) + \ONE)\\ + (a + \ONE) \cdot (\ONE + \ONE) \end{array} \] -\item What is the purpose of the record regular expression - in the Sulzmann \& Lu algorithm? +\item What is the purpose of the record regular expression in + the Sulzmann \& Lu algorithm? %\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as