\documentclass{article}
\usepackage{../style}
\begin{document}
\section*{Homework 1}
\begin{enumerate}
\item {\bf (Optional)} If you want to run the code presented
in the lectures, install the Scala programming language
available (for free) from
\begin{center}
\url{http://www.scala-lang.org}
\end{center}
If you want to follow the code I present during the
lectures, read the handout about Scala.
\item {\bf (Optional)} Have a look at the crawler programs.
Can you find a usage for them in your daily programming
life? Can you improve them? (For example in cases there
are links that appear on different recursion levels, the
crawlers visit such web-pages several times. Can this be
avoided?)
\item Read the handout of the first lecture and the handout
about notation. Make sure you understand the concepts of
strings and languages.
\item In the context of the AFL-course, what is meant by the
term \emph{language}?
\item Give the definition for regular expressions. What is the
meaning of a regular expression?
\item Assume the concatenation operation of two strings is
written as $s_1 @ s_2$. Define the operation of
\emph{concatenating}, written $\_ \,@\, \_$ two sets of
strings.
\item Assume a set $A$ contains 4 strings and a set $B$ 7
strings, how many strings are in $A @ B$?
\item How is the power of a language defined? (Hint: There are
two rules, one for $\_^0$ and one for
$\_^{n+1}$.)
\item How many regular expressions are there to match the
string $abc$? How many if they cannot include
$\epsilon$ and $\varnothing$? How many if they are also
not allowed to contain stars? How many if they are also
not allowed to contain $\_ + \_$?
\item When are two regular expressions equivalent? Can you
think of instances where two regular expressions match
the same strings, but it is not so obvious that they do? For
example $a + b$ and $b + a$ do not count\ldots they
obviously match the same strings, namely $[a]$ and $[b]$.
\end{enumerate}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: