\documentclass{article}+ −
\usepackage{../style}+ −
+ −
\begin{document}+ −
+ −
\section*{Homework 2}+ −
+ −
\HEADER+ −
+ −
\begin{enumerate}+ −
\item What is the difference between \emph{basic} regular expressions + −
and \emph{extended} regular expressions?+ −
+ −
\item What is the language recognised by the regular+ −
expressions $(\ZERO^*)^*$.+ −
+ −
\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 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 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^+) ++ −
(b^*\cdot b^+)$ define the same language?+ −
+ −
\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 \}$. + −
+ −
\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: + −