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