diff -r 70c307641d05 -r 1e4da6d2490c hws/hw02.tex --- a/hws/hw02.tex Mon Sep 22 13:42:14 2014 +0100 +++ b/hws/hw02.tex Fri Sep 26 14:06:55 2014 +0100 @@ -9,40 +9,53 @@ \section*{Homework 2} \begin{enumerate} -\item Review the first handout about sets of strings and read the second handout. -Assuming the alphabet is $\{a, b\}$, decide which of the following equations are true -in general for arbitrary languages $A$, $B$ and $C$: +\item Review the first handout about sets of strings and read + the second handout. Assuming the alphabet is $\{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 +(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. +\noindent In case an equation is true, give an explanation; +otherwise give a counter-example. -\item What is the meaning of a regular expression? Give an inductive definition. +\item What is the meaning of a regular expression? Give an + inductive definition. -\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 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 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 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$ and $b$. Is $r$ nullable? +\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} -$\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$ + +\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. + \end{enumerate} \end{document}