hws/hw02.tex
changeset 258 1e4da6d2490c
parent 132 04264d0c43bb
child 267 a1544b804d1e
--- a/hws/hw02.tex	Mon Sep 22 13:42:14 2014 +0100
+++ b/hws/hw02.tex	Fri Sep 26 14:06:55 2014 +0100
@@ -9,40 +9,53 @@
 \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 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$:
+
 \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
+(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 What is the meaning of a regular expression? Give an inductive definition.
+\item What is the meaning of a regular expression? Give an
+      inductive definition.
 
-\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 = \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)^*$.
+\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)^*$.
 
-\item Given the regular expression $r = (a \cdot b + b)^*$. Compute what the derivative of $r$ is with respect to
-$a$ and $b$. 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
-\begin{center}
-$\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$
+      
+\begin{center} 
+  $\textit{nullable}(r) \quad \text{if and only if} 
+  \quad [] \in L(r)$ 
 \end{center}
 
+  Write down clearly in each case what you need to prove and
+  what are the assumptions. 
+  
 \end{enumerate}
 
 \end{document}