--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hw04.tex	Thu Oct 11 16:52:21 2012 +0100
@@ -0,0 +1,55 @@
+\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: