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