\documentclass{article}

\usepackage{charter}

\usepackage{hyperref}

\usepackage{amssymb}

\usepackage{amsmath}

\begin{document}

\section*{Homework 4}

\begin{enumerate}

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

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

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

Note, you can only use regular expressions of the form 

\begin{center}

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

\end{center}

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

and returns a boolean.\footnote{In an earlier version there was an error.} The 

function should satisfy the following property:

\begin{center}

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

\end{center}

\item Define the tokens and regular expressions for a language

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

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

in this language be lexed?

\begin{itemize}

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

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

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

\end{itemize}

\item (Optional) The tokenizer in \texttt{regexp3.scala} takes as

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

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

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

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

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

match the regular expression.

\end{enumerate}

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: