1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 

     7 \begin{document}

     8 

     9 \section*{Homework 3}

    10 

    11 \begin{enumerate}

    12 \item Assume you have an alphabet consisting of the letters $a$, $b$ and $c$ only.

    13 (a) Find a regular expression that recognises the two strings $ab$ and $ac$. (b)

    14 Find a regular expression that matches all strings \emph{except} these two strings.

    15 Note, you can only use regular expressions of the form 

    16 \begin{center}

    17 $r ::= \varnothing \;|\; \epsilon \;|\; c  \;|\; r_1 + r_2  \;|\; r_1 \cdot r_2 \;|\; r^*$

    18 \end{center}

    19 

    20 \item Define the function $zeroable$ which takes a regular expression as argument

    21 and returns an integer. The function should satisfy the following property:

    22 \begin{center}

    23 $zeroable(r)$ \;if and only if\; $L(r) = \varnothing$

    24 \end{center}

    25 

    26 \end{enumerate}

    27 

    28 \end{document}

    29 

    30 %%% Local Variables: 

    31 %%% mode: latex

    32 %%% TeX-master: t

    33 %%% End: