27 crawlers visit such web-pages several times. Can this be |
27 crawlers visit such web-pages several times. Can this be |
28 avoided?) |
28 avoided?) |
29 |
29 |
30 \item Read the handout of the first lecture and the handout |
30 \item Read the handout of the first lecture and the handout |
31 about notation. Make sure you understand the concepts of |
31 about notation. Make sure you understand the concepts of |
32 strings and languages. In the context of the AFL-course, |
32 strings and languages. In the context of the CFL-course, |
33 what is meant by the term \emph{language}? |
33 what is meant by the term \emph{language}? |
34 |
34 |
35 \item Give the definition for regular expressions. What is the |
35 \item Give the definition for regular expressions---this is an |
|
36 inductive datatype. What is the |
36 meaning of a regular expression? (Hint: The meaning is |
37 meaning of a regular expression? (Hint: The meaning is |
37 defined recursively.) |
38 defined recursively.) |
38 |
39 |
39 \item Assume the concatenation operation of two strings is |
40 \item Assume the concatenation operation of two strings is |
40 written as $s_1 @ s_2$. Define the operation of |
41 written as $s_1 @ s_2$. Define the operation of |
41 \emph{concatenating} two sets of strings. This operation |
42 \emph{concatenating} two sets of strings. This operation |
42 is also written as $\_ \,@\, \_$. According to |
43 is also written as $\_ \,@\, \_$. According to |
43 this definition, what is $A \,@\, \{\}$ equal to? |
44 this definition, what is $A \,@\, \{\}$ equal to? |
|
45 Is in general $A\,@\,B$ equal to $B\,@\,A$? |
44 |
46 |
45 \item Assume a set $A$ contains 4 strings and a set $B$ |
47 \item Assume a set $A$ contains 4 strings and a set $B$ |
46 contains 7 strings. None of the strings is the empty |
48 contains 7 strings. None of the strings is the empty |
47 string. How many strings are in $A \,@\, B$? |
49 string. How many strings are in $A \,@\, B$? |
48 |
50 |