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