\documentclass{article}+
−
\usepackage{charter}+
−
\usepackage{hyperref}+
−
\usepackage{amssymb}+
−
\usepackage{amsmath}+
−
+
−
\begin{document}+
−
+
−
\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$:+
−
\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 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 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$ and $b$. 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)$+
−
\end{center}+
−
+
−
\end{enumerate}+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−