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