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