1 \documentclass{article}

     2 \usepackage{charter}

     3 \usepackage{hyperref}

     4 \usepackage{amssymb}

     5 \usepackage{amsmath}

     6 

     7 \begin{document}

     8 

     9 \section*{Homework 4}

    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 \item (Optional) The tokenizer in \texttt{regexp3.scala} takes as

    39 argument a string and a list of rules. The result is a list of tokens. Improve this tokenizer so 

    40 that it filters out all comments and whitespace from the result.

    41 

    42 \item (Optional) Modify the tokenizer in \texttt{regexp2.scala} so that it

    43 implements the \texttt{findAll} function. This function takes a regular

    44 expressions and a string, and returns all substrings in this string that 

    45 match the regular expression.

    46 \end{enumerate}

    47 

    48 

    49 

    50 \end{document}

    51 

    52 %%% Local Variables: 

    53 %%% mode: latex

    54 %%% TeX-master: t

    55 %%% End: