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