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