\documentclass{article}
\usepackage{charter}
\usepackage{hyperref}
\usepackage{amssymb}
\usepackage{amsmath}

\newcommand{\dn}{\stackrel{\mbox{\scriptsize def}}{=}}% for definitions

\begin{document}

\section*{Homework 4}

\begin{enumerate}
\item Why is every finite set of strings a regular language?


\item Give an automaton that can recognise the language 
$L(a^*\cdot b\cdot b^*\cdot(a\cdot a^*\cdot b\cdot b^*)^*)$.

\item Assume that $s^{-1}$ stands for the operation of reversing a
string $s$. Given the following \emph{reversing} function on regular 
expressions

\begin{center}
\begin{tabular}{r@{\hspace{1mm}}c@{\hspace{1mm}}l}
$rev(\varnothing)$   & $\dn$ & $\varnothing$\\
$rev(\epsilon)$         & $\dn$ & $\epsilon$\\
$rev(c)$                      & $\dn$ & $c$\\
$rev(r_1 + r_2)$        & $\dn$ & $rev(r_1) + rev(r_2)$\\
$rev(r_1 \cdot r_2)$  & $\dn$ & $rev(r_2) \cdot rev(r_1)$\\
$rev(r^*)$                   & $\dn$ & $rev(r)^*$\\
\end{tabular}
\end{center}


and the set

\begin{center}
$Rev\,A \dn \{s^{-1} \;|\; s \in A\}$
\end{center}

prove whether

\begin{center}
$L(rev(r)) = Rev (L(r))$
\end{center}

holds.

\item Palindromes

\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: 
