\documentclass{article}
\usepackage{../style}

\begin{document}

\section*{Homework 2}

\HEADER

\begin{enumerate}

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

      \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.

\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 Decide whether the following two regular expressions are
      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 Prove that for all regular expressions $r$ we have
      
\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. 
  
\item Define what is meant by the derivative of a regular
      expressions with respect 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?

\item Define the function $zeroable$ by recursion over regular
      expressions. This function should satisfy the property

  \[
  zeroable(r) \;\;\text{if and only if}\;\;L(r) = \{\}\qquad(*)
  \]

      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 $(*)$:

  \[
  zeroable(\sim r) \dn \neg(zeroable(r))
  \]

      Find a counter example?

\item Give a regular expressions that can recognise all
      strings from the language $\{a^n\;|\;\exists k.\; n = 3 k
      + 1 \}$. 
      
\item Give a regular expression that can recognise an odd 
number of $a$s or an even number of $b$s.     

\item \POSTSCRIPT  
\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: