\documentclass{article}

\usepackage{../style}

\begin{document}

\section*{Homework 2}

\HEADER

\begin{enumerate}

\item What is the difference between \emph{basic} regular expressions  

\item What is the language recognised by the regular

\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---for example the JSON format for numbers

      explicitly forbids this.

\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 Give an argument for why the following holds:

\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^+) +

\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

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