% !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+ −
+ −
\begin{center}+ −
\url{http://www.scala-lang.org}+ −
\end{center}+ −
+ −
and the Ammonite REPL from+ −
+ −
\begin{center}+ −
\url{https://ammonite.io}+ −
\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? 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: + −