hws/hw04.tex
changeset 401 5d85dc9779b1
parent 359 db106e5b7c4d
child 444 3056a4c071b0
--- 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