\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$:

(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

\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 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 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$, $b$ and $c$. Is $r$ nullable?

\begin{center} 

  $\textit{nullable}(r) \quad \text{if and only if} 

  \quad [] \in L(r)$ 

  Write down clearly in each case what you need to prove and

  what are the assumptions.