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