631
|
1 |
% !TEX program = xelatex
|
0
|
2 |
\documentclass{article}
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
3 |
\usepackage{../style}
|
0
|
4 |
|
|
5 |
\begin{document}
|
|
6 |
|
|
7 |
\section*{Homework 1}
|
|
8 |
|
331
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
|
0
|
11 |
\begin{enumerate}
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
\item {\bf (Optional)} If you want to run the code presented
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
in the lectures, install the Scala programming language
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
available (for free) from
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
16 |
|
743
|
17 |
\begin{center}
|
|
18 |
\url{http://www.scala-lang.org}
|
|
19 |
\end{center}
|
|
20 |
|
|
21 |
and the Ammonite REPL from
|
|
22 |
|
|
23 |
\begin{center}
|
|
24 |
\url{https://ammonite.io}
|
|
25 |
\end{center}
|
0
|
26 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
If you want to follow the code I present during the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
lectures, read the handout about Scala.
|
0
|
29 |
|
639
|
30 |
%\item {\bf (Optional)} Have a look at the crawler programs.
|
|
31 |
% Can you find a usage for them in your daily programming
|
|
32 |
% life? Can you improve them? For example in cases there
|
|
33 |
% are links that appear on different recursion levels, the
|
|
34 |
% crawlers visit such web-pages several times. Can this be
|
|
35 |
% avoided? Also, the crawlers flag as problematic any page
|
|
36 |
% that gives an error, but probably only 404 Not Found
|
|
37 |
% errors should be flagged. Can you change that?)
|
104
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
|
640
|
39 |
\item {\bf (Optional)} Have a look at the catastrophic backtracking
|
|
40 |
programs uploaded on KEATS. Convince yourself that they really require
|
|
41 |
a lot of computation time. If you have similar examples in your own
|
|
42 |
favourite programming language, I am happy to hear about it.
|
|
43 |
|
|
44 |
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
\item Read the handout of the first lecture and the handout
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
about notation. Make sure you understand the concepts of
|
498
|
47 |
strings and languages. In the context of the CFL-course,
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
what is meant by the term \emph{language}?
|
9
|
49 |
|
550
|
50 |
\item Give the definition for regular expressions---this is an
|
498
|
51 |
inductive datatype. What is the
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
meaning of a regular expression? (Hint: The meaning is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
defined recursively.)
|
0
|
54 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
\item Assume the concatenation operation of two strings is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
written as $s_1 @ s_2$. Define the operation of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
\emph{concatenating} two sets of strings. This operation
|
394
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
is also written as $\_ \,@\, \_$. According to
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
this definition, what is $A \,@\, \{\}$ equal to?
|
498
|
60 |
Is in general $A\,@\,B$ equal to $B\,@\,A$?
|
0
|
61 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
\item Assume a set $A$ contains 4 strings and a set $B$
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
contains 7 strings. None of the strings is the empty
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
64 |
string. How many strings are in $A \,@\, B$?
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
65 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
\item How is the power of a language defined? (Hint: There are two
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
rules, one for $\_^0$ and one for $\_^{n+1}$.)
|
109
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
68 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
69 |
\item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings
|
438
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
70 |
are in $A^4$? (2) Consider also the case of $A^4$ where one of
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
71 |
the strings in $A$ is the empty string, for example $A =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
72 |
\{[a], [b], [c], []\}$.
|
293
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
73 |
|
507
|
74 |
\item (1) How many basic regular expressions are there to match
|
444
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
75 |
the string $abcd$? (2) How many if they cannot include
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
76 |
$\ONE$ and $\ZERO$? (3) How many if they are also not
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
77 |
allowed to contain stars? (4) How many if they are also
|
401
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
78 |
not allowed to contain $\_ + \_$?
|
0
|
79 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
80 |
\item When are two regular expressions equivalent? Can you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
81 |
think of instances where two regular expressions match
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
82 |
the same strings, but it is not so obvious that they do?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
83 |
For example $a + b$ and $b + a$ do not count\ldots they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
84 |
obviously match the same strings, namely $[a]$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
85 |
$[b]$.
|
403
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
86 |
|
416
|
87 |
\item What is meant by the notions \emph{evil regular expressions}
|
726
|
88 |
and by \emph{catastrophic backtracking}?
|
|
89 |
|
|
90 |
\item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$,
|
|
91 |
which of the following regular expressions are equyivalent
|
|
92 |
|
|
93 |
\begin{center}
|
|
94 |
\begin{tabular}{ll}
|
|
95 |
1) & $(ab + bb)^* \cdot (a + b)^*$\\ % no
|
|
96 |
2) & $(a + b)^* \cdot (ba + bb + b) \cdot (a + b)^*$\\ % yes
|
|
97 |
3) & $(a + b)^* \cdot (a + b) \cdot (a + b)^*$ % no
|
|
98 |
\end{tabular}
|
|
99 |
\end{center}
|
|
100 |
|
403
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
101 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
102 |
\item \POSTSCRIPT
|
0
|
103 |
\end{enumerate}
|
|
104 |
|
|
105 |
\end{document}
|
|
106 |
|
|
107 |
%%% Local Variables:
|
|
108 |
%%% mode: latex
|
|
109 |
%%% TeX-master: t
|
|
110 |
%%% End:
|