hws/hw02.tex
author Christian Urban <christian dot urban at kcl dot ac dot uk>
Fri, 10 Oct 2014 16:59:22 +0100
changeset 267 a1544b804d1e
parent 258 1e4da6d2490c
child 292 7ed2a25dd115
permissions -rw-r--r--
updated homeworks

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

\begin{document}

\section*{Homework 2}

\begin{enumerate}
\item What is the language recognised by the regular expressions
  $(\varnothing^*)^*$.

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

\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 mean by the derivative of a regular expressions
  with respoect 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?
\end{enumerate}

\end{document}

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