1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 

     7 \begin{document}

     8 

     9 \section*{Homework 2}

    10 

    11 \begin{enumerate}

    12 \item Give regular expressions for (a) decimal numbers and for (b) binary numbers. 

    13 (Hint: Observe that the empty string is not a number. Also observe that leading 0s 

    14 are normally not written.)

    15 

    16 \item Decide whether the following two regular expressions are equivalent $(\epsilon + a)^* \equiv^? a^*$ and 

    17 $(a \cdot b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$.

    18 

    19 \item Given the regular expression $r = (a \cdot b + b)^*$. Compute what the derivative of $r$ is with respect to

    20 $a$ and $b$. Is $r$ nullable?

    21 

    22 \item What is a regular language?

    23 

    24 \item Prove that for all regular expressions $r$ we have

    25 \begin{center}

    26 $\text{nullable}(r)$ \quad if and only if \quad $\texttt{""} \in L(r)$

    27 \end{center}

    28 

    29 \end{enumerate}

    30 

    31 \end{document}

    32 

    33 %%% Local Variables: 

    34 %%% mode: latex

    35 %%% TeX-master: t

    36 %%% End: