7 \begin{document}

     7 \begin{document}

     8 

     8 

     9 \section*{Homework 3}

     9 \section*{Homework 3}

    10 

    10 

    11 \begin{enumerate}

    11 \begin{enumerate}

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

    14 \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)

    15 (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.

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

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

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

    16 \begin{center}

    18 \begin{center}

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

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

    18 \end{center}

    20 \end{center}

    19 

    21 

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

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

    22 function should satisfy the following property:

    24 function should satisfy the following property:

    23 \begin{center}

    25 \begin{center}

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

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

    25 \end{center}

    27 \end{center}

    26 

    28