
diff -r ae039d6ae3f2 -r a1544b804d1e hws/hw02.tex
--- a/hws/hw02.tex	Mon Oct 06 20:55:16 2014 +0100
+++ b/hws/hw02.tex	Fri Oct 10 16:59:22 2014 +0100
@@ -1,50 +1,44 @@
 \documentclass{article}
-\usepackage{charter}
-\usepackage{hyperref}
-\usepackage{amssymb}
-\usepackage{amsmath}
+\usepackage{../style}
 
 \begin{document}
 
 \section*{Homework 2}
 
 \begin{enumerate}
-\item Review the first handout about sets of strings and read
-      the second handout. Assuming the alphabet is $\{a, b\}$,
-      decide which of the following equations are true in
-      general for arbitrary languages $A$, $B$ and $C$:
+\item What is the language recognised by the regular expressions
+  $(\varnothing^*)^*$.
 
-\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}
+\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$:
 
-\noindent In case an equation is true, give an explanation;
-otherwise give a counter-example.
-
-\item What is the meaning of a regular expression? Give an
-      inductive definition.
+  \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}
 
-\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?
+  \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 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 $(\epsilon + 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
       
@@ -56,6 +50,25 @@
   Write down clearly in each case what you need to prove and
   what are the assumptions. 
   
+\item Define what is mean by the derivative of a regular expressions
+  with respoect to a character. (Hint: The derivative is defined
+  recursively.)
+
+\item Assume the set $Der$ is defined as
+
+  \begin{center}
+    $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?
+
+\item Give a regular expression over the alphabet $\{a,b\}$
+  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?
 \end{enumerate}
 
 \end{document}




