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 a boolean.\footnote{In an earlier version there was an error.} The 

    22 function should satisfy the following property:

    23 \begin{center}

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

    25 \end{center}

    26 

    27 \item Define the tokens and regular expressions for a language

    28 consisting of numbers, left-parenthesis (, right-parenthesis ),

    29 identifiers and the operations $+$, $-$ and $*$. Can the following strings 

    30 in this language be lexed?

    31 

    32 \begin{itemize}

    33 \item \texttt{"}$(a + 3) * b$\texttt{"}

    34 \item \texttt{"}$)()++ -33$\texttt{"}

    35 \item \texttt{"}$(a / 3) * 3$\texttt{"}

    36 \end{itemize}

    37 

    38 

    39 In case they can, can you give the corresponding token sequences.

    40 \end{enumerate}

    41 

    42 

    43 

    44 \end{document}

    45 

    46 %%% Local Variables: 

    47 %%% mode: latex

    48 %%% TeX-master: t

    49 %%% End: