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