% !TEX program = xelatex

\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

      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? Also, the crawlers flag as problematic any page

%      that gives an error, but probably only 404 Not Found

%      errors should be flagged. Can you change that?)

\item {\bf (Optional)} Have a look at the catastrophic backtracking

  programs uploaded on KEATS. Convince yourself that they really require

  a lot of computation time. If you have similar examples in your own

  favourite programming language, I am happy to hear about it.

\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 CFL-course,

      what is meant by the term \emph{language}?

\item Give the definition for regular expressions---this is an

      inductive datatype. 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} two sets of strings. This operation

      is also written as $\_ \,@\, \_$. According to 

      this definition, what is $A \,@\, \{\}$ equal to?

      Is in general $A\,@\,B$ equal to $B\,@\,A$?

\item Assume a set $A$ contains 4 strings and a set $B$

      contains 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]\}$. (1) How many strings

      are in $A^4$? (2) Consider also the case of $A^4$ where one of

      the strings in $A$ is the empty string, for example $A =

      \{[a], [b], [c], []\}$.

\item (1) How many basic regular expressions are there to match

      the string $abcd$? (2) How many if they cannot include

      $\ONE$ and $\ZERO$? (3) How many if they are also not

      allowed to contain stars? (4) 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]$.

\item What is meant by the notions \emph{evil regular expressions}

  and by \emph{catastrophic backtracking}?

\item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$,

  which of the following regular expressions are equyivalent

\begin{center}

\begin{tabular}{ll}    

  1) & $(ab + bb)^* \cdot (a + b)^*$\\                     % no

  2) & $(a + b)^* \cdot (ba + bb + b) \cdot (a + b)^*$\\   % yes

  3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$           % no

\end{tabular}

\end{center}

\item \POSTSCRIPT  

\end{enumerate}

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: