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 |
|
331
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
8 |
\HEADER
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
9 |
|
0
|
10 |
\begin{enumerate}
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
11 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
12 |
\item {\bf (Optional)} If you want to run the code presented in the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
13 |
lectures, install the Scala programming language available (for
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
14 |
free) from
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
15 |
|
0
|
16 |
\begin{center}
|
|
17 |
\url{http://www.scala-lang.org}
|
|
18 |
\end{center}
|
|
19 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
20 |
If you want to follow the code I present during the lectures,
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
21 |
read the handout about Scala.
|
0
|
22 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
23 |
\item {\bf (Optional)} Have a look at the crawler programs. Can you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
24 |
find a usage for them in your daily programming life? Can you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
25 |
improve them? (For example in cases there are links that appear on
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
26 |
different recursion levels, the crawlers visit such web-pages
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
27 |
several times. Can this be avoided?)
|
104
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
28 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
29 |
\item Read the handout of the first lecture and the handout about
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
30 |
notation. Make sure you understand the concepts of strings and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
31 |
languages. 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
|
32 |
term \emph{language}?
|
9
|
33 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
34 |
\item Give the definition for regular expressions. What is the
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
35 |
meaning of a regular expression? (Hint: The meaning is
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
36 |
defined recursively.)
|
0
|
37 |
|
355
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. This operation
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
41 |
is also written as $\_ \,@\, \_$.
|
0
|
42 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
43 |
\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
|
44 |
contains 7 strings. None of the strings is the empty
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
45 |
string. How many strings are in $A \,@\, B$?
|
249
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
46 |
|
267
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
47 |
\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
|
48 |
rules, one for $\_^0$ and one for $\_^{n+1}$.)
|
109
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
49 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
50 |
\item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
51 |
are in $A^4$? (2) Consider the case of $A^4$ where one of
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
52 |
the strings in $A$ is the empty string, for example $A =
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
53 |
\{[a], [b], [c], []\}$.
|
293
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
54 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
55 |
\item How many basic regular expressions are there to match
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
56 |
the string $abcd$? (ii) How many if they cannot include
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
57 |
$\epsilon$ and $\varnothing$? (iii) How many if they are
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
58 |
also not allowed to contain stars? (iv) How many if they
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
59 |
are also not allowed to contain $\_ + \_$?
|
0
|
60 |
|
355
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
61 |
\item When are two regular expressions equivalent? Can you
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
62 |
think of instances where two regular expressions match
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
63 |
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
|
64 |
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
|
65 |
obviously match the same strings, namely $[a]$ and
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
66 |
$[b]$.
|
Christian Urban <christian dot urban at kcl dot ac dot uk>
diff
changeset
|
67 |
|
0
|
68 |
\end{enumerate}
|
|
69 |
|
|
70 |
\end{document}
|
|
71 |
|
|
72 |
%%% Local Variables:
|
|
73 |
%%% mode: latex
|
|
74 |
%%% TeX-master: t
|
|
75 |
%%% End:
|