--- 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