\documentclass{article}

\usepackage{../style}

\newcommand{\solution}[1]{%

  \begin{quote}\sf%

    #1%

  \end{quote}}

\renewcommand{\solution}[1]{}

\begin{document}

\section*{Homework 2}

\HEADER

\begin{enumerate}

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

  and \emph{extended} regular expressions?

  \solution{Basic regular expressions are $\ZERO$, $\ONE$, $c$, $r_1 + r_2$,

    $r_1 \cdot r_2$, $r^*$. The extended ones are the bounded

    repetitions, not, etc.}

\item What is the language recognised by the regular

  expressions $(\ZERO^*)^*$.

  \solution{$L(\ZERO^*{}^*) = \{[]\}$,

    remember * always includes the empty string}

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

      \solution{1 + 3 are equal; 2 + 4 are not. Interesting is 4 where

      $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$}

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

      \solution{$r_1$ and $r_2$ can match the empty string only, $r_3$ can

        match $[]$, $a$, $aa$, ....}

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

      \solution{Just numbers without leading 0s: $0 + (1..9)\cdot(0..1)^*$;

        can be extended to decimal; similar for binary numbers

      }

\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)^*$.

      \solution{Both are equivalent, but why the second? Essentially you have to show that each string in one set is in the other. For 2 this means you can do an induction proof that $(ab)^na$ is the same string as $a(ba)^n$, where the former is in the first set and the latter in the second.}

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

  if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$.

  \solution{This was from last week; I just explicitly added it here.}

\item Define what is meant by the derivative of a regular

      expressions with respect to a character. (Hint: The

      derivative is defined recursively.)

      \solution{the recursive function for $der$}

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

      \solution{Main property is $L(der\,c\,r) = Der\,c\,(L(r))$.}

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

   \solution{No, the first one can match for example abababababbbbb}

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

      \solution{$a(aaa)^*$}

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