
diff -r e4afe3f46c29 -r 5d85dc9779b1 hws/hw02.tex
--- a/hws/hw02.tex	Wed Apr 06 12:18:54 2016 +0100
+++ b/hws/hw02.tex	Wed Apr 06 15:55:01 2016 +0100
@@ -8,39 +8,42 @@
 \HEADER
 
 \begin{enumerate}
-\item What is the language recognised by the regular expressions
-  $(\varnothing^*)^*$.
+
+\item What is the language recognised by the regular
+      expressions $(\ZERO^*)^*$.
 
-\item Review the first handout about sets of strings and read the
-  second handout. Assuming the alphabet is the set $\{a, b\}$, decide
-  which of the following equations are true in general for arbitrary
-  languages $A$, $B$ and $C$:
+\item Review the first handout about sets of strings and read
+      the second handout. Assuming the alphabet is the set
+      $\{a, b\}$, decide which of the following equations are
+      true in general for arbitrary languages $A$, $B$ and
+      $C$:
 
-  \begin{eqnarray}
-    (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\
-    A^* \cup B^*   & =^? & (A \cup B)^*\nonumber\\
-    A^* @ A^*      & =^? & A^*\nonumber\\
-    (A \cap B)@ C  & =^? & (A@C) \cap (B@C)\nonumber
-  \end{eqnarray}
+      \begin{eqnarray}
+      (A \cup B) @ C & =^? & A @ C \cup B @ C\nonumber\\
+      A^* \cup B^*   & =^? & (A \cup B)^*\nonumber\\
+      A^* @ A^*      & =^? & A^*\nonumber\\
+      (A \cap B)@ C  & =^? & (A@C) \cap (B@C)\nonumber
+      \end{eqnarray}
 
-  \noindent In case an equation is true, give an explanation; otherwise
-  give a counter-example.
+      \noindent In case an equation is true, give an
+      explanation; otherwise give a counter-example.
 
-\item Given the regular expressions $r_1 = \epsilon$ and $r_2 =
-  \varnothing$ and $r_3 = a$. How many strings can the regular
-  expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match?
+\item Given the regular expressions $r_1 = \ONE$ and $r_2 =
+      \ZERO$ and $r_3 = a$. How many strings can the regular
+      expressions $r_1^*$, $r_2^*$ and $r_3^*$ each match?
 
-\item Give regular expressions for (a) decimal numbers and for (b)
-  binary numbers. (Hint: Observe that the empty string is not a
-  number. Also observe that leading 0s are normally not written.)
+\item Give regular expressions for (a) decimal numbers and for
+      (b) binary numbers. (Hint: Observe that the empty string
+      is not a number. Also observe that leading 0s are
+      normally not written.)
 
 \item Decide whether the following two regular expressions are
-  equivalent $(\epsilon + a)^* \equiv^? a^*$ and $(a \cdot b)^* \cdot
-  a \equiv^? a \cdot (b \cdot a)^*$.
+      equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot
+      b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.
 
-\item Given the regular expression $r = (a \cdot b + b)^*$.  Compute
-  what the derivative of $r$ is with respect to $a$, $b$ and $c$. Is
-  $r$ nullable?
+\item Given the regular expression $r = (a \cdot b + b)^*$.
+      Compute what the derivative of $r$ is with respect to
+      $a$, $b$ and $c$. Is $r$ nullable?
 
 \item Prove that for all regular expressions $r$ we have
       
@@ -49,8 +52,8 @@
   \quad [] \in L(r)$ 
 \end{center}
 
-  Write down clearly in each case what you need to prove and
-  what are the assumptions. 
+      Write down clearly in each case what you need to prove
+      and what are the assumptions. 
   
 \item Define what is meant by the derivative of a regular
       expressions with respect to a character. (Hint: The
@@ -62,42 +65,42 @@
     $Der\,c\,A \dn \{ s \;|\;  c\!::\!s \in A\}$
   \end{center}
 
-  What is the relation between $Der$ and the notion of derivative of
-  regular expressions?
+      What is the relation between $Der$ and the notion of
+      derivative of regular expressions?
 
 \item Give a regular expression over the alphabet $\{a,b\}$
-  recognising all strings that do not contain any substring $bb$ and
-  end in $a$.
+      recognising all strings that do not contain any
+      substring $bb$ and end in $a$.
 
-\item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) + (b^*\cdot b^+)$ define 
-  the same language?
+\item Do $(a + b)^* \cdot b^+$ and $(a^* \cdot b^+) +
+      (b^*\cdot b^+)$ define the same language?
 
 \item Define the function $zeroable$ by recursion over regular
-  expressions. This function should satisfy the property
+      expressions. This function should satisfy the property
 
   \[
-  zeroable(r) \;\;\text{if and only if}\;\;L(r) = \varnothing\qquad(*)
+  zeroable(r) \;\;\text{if and only if}\;\;L(r) = \{\}\qquad(*)
   \]
 
-  The function $nullable$ for the not-regular expressions can be defined
-  by 
+      The function $nullable$ for the not-regular expressions
+      can be defined by 
 
   \[
   nullable(\sim r) \dn \neg(nullable(r))
   \]
 
-  Unfortunately, a similar definition for $zeroable$ does not satisfy
-  the property in $(*)$:
+      Unfortunately, a similar definition for $zeroable$ does
+      not satisfy the property in $(*)$:
 
   \[
   zeroable(\sim r) \dn \neg(zeroable(r))
   \]
 
-  Find out why?
+      Find out why?
 
-\item Give a regular expressions that can recognise all strings from the 
-  language $\{a^n\;|\;\exists k. n = 3 k + 1 \}$.
-\end{enumerate}
+\item Give a regular expressions that can recognise all
+      strings from the language $\{a^n\;|\;\exists k.\; n = 3 k
+      + 1 \}$. \end{enumerate}
 
 \end{document}
 




