\documentclass{article}
\usepackage{../style}

\begin{document}

\section*{Homework 1}

\HEADER

\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.  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? (Hint: The meaning is defined recursively.)

\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. None
  of the strings is the empty string. 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 Let $A = \{[a], [b], [c], [d]\}$. How many strings are in $A^4$?
  Consider the case of $A^4$ where one of the strings in $A$ is the 
  empty string, for example $A = \{[a], [b], [c], []\}$.

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