0
|
1 |
\documentclass{article}
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
2 |
\usepackage{../style}
|
0
|
3 |
|
|
4 |
\begin{document}
|
|
5 |
|
|
6 |
\section*{Homework 1}
|
|
7 |
|
|
8 |
\begin{enumerate}
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
10 |
\item {\bf (Optional)} If you want to run the code presented
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
in the lectures, install the Scala programming language
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
available (for free) from
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
|
0
|
14 |
\begin{center}
|
|
15 |
\url{http://www.scala-lang.org}
|
|
16 |
\end{center}
|
|
17 |
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
18 |
If you want to follow the code I present during the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
19 |
lectures, read the handout about Scala.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
\item {\bf (Optional)} Have a look at the crawler programs.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
22 |
Can you find a usage for them in your daily programming
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
life? Can you improve them? (For example in cases there
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
are links that appear on different recursion levels, the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
crawlers visit such web-pages several times. Can this be
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
avoided?)
|
0
|
27 |
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
\item Read the handout of the first lecture and the handout
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
about notation. Make sure you understand the concepts of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
strings and languages.
|
104
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
32 |
\item In the context of the AFL-course, what is meant by the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
33 |
term \emph{language}?
|
9
|
34 |
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
\item Give the definition for regular expressions. What is the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
meaning of a regular expression?
|
0
|
37 |
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
38 |
\item Assume the concatenation operation of two strings is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
39 |
written as $s_1 @ s_2$. Define the operation of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
40 |
\emph{concatenating} two sets of strings.
|
0
|
41 |
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
42 |
\item Assume a set $A$ contains 4 strings and a set $B$ 7
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
strings, how many strings are in $A @ B$?
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
44 |
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
\item How is the power of a language defined? (Hint: There are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
two rules, one for $\_^0$ and one for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
$\_^{n+1}$.)
|
109
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
48 |
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
\item How many regular expressions are there to match the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
string $abc$? (How many if they cannot include
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
$\epsilon$ and $\varnothing$? How many if they also are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
not allowed to contain stars? How many if they also are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
not allowed to contain $\_ + \_$?)
|
0
|
54 |
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
\item When are two regular expressions equivalent? Can you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
think of instances where two regular expressions are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
equivalent, but it is not so obvious that they are? For
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
example $a + b$ and $b + a$ do not count\ldots they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
are obviously equivalent.
|
0
|
60 |
|
|
61 |
\end{enumerate}
|
|
62 |
|
|
63 |
\end{document}
|
|
64 |
|
|
65 |
%%% Local Variables:
|
|
66 |
%%% mode: latex
|
|
67 |
%%% TeX-master: t
|
|
68 |
%%% End:
|