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