29 \item Read the handout of the first lecture and the handout about |
29 \item Read the handout of the first lecture and the handout about |
30 notation. Make sure you understand the concepts of strings and |
30 notation. Make sure you understand the concepts of strings and |
31 languages. In the context of the AFL-course, what is meant by the |
31 languages. In the context of the AFL-course, what is meant by the |
32 term \emph{language}? |
32 term \emph{language}? |
33 |
33 |
34 \item Give the definition for regular expressions. What is the meaning |
34 \item Give the definition for regular expressions. What is the |
35 of a regular expression? (Hint: The meaning is defined recursively.) |
35 meaning of a regular expression? (Hint: The meaning is |
|
36 defined recursively.) |
36 |
37 |
37 \item Assume the concatenation operation of two strings is written as |
38 \item Assume the concatenation operation of two strings is |
38 $s_1 @ s_2$. Define the operation of \emph{concatenating}, written |
39 written as $s_1 @ s_2$. Define the operation of |
39 $\_ \,@\, \_$, two sets of strings. |
40 \emph{concatenating} two sets of strings. This operation |
|
41 is also written as $\_ \,@\, \_$. |
40 |
42 |
41 \item Assume a set $A$ contains 4 strings and a set $B$ 7 strings. None |
43 \item Assume a set $A$ contains 4 strings and a set $B$ |
42 of the strings is the empty string. How many strings are in $A \,@\, B$? |
44 contains 7 strings. None of the strings is the empty |
|
45 string. How many strings are in $A \,@\, B$? |
43 |
46 |
44 \item How is the power of a language defined? (Hint: There are two |
47 \item How is the power of a language defined? (Hint: There are two |
45 rules, one for $\_^0$ and one for $\_^{n+1}$.) |
48 rules, one for $\_^0$ and one for $\_^{n+1}$.) |
46 |
49 |
47 \item Let $A = \{[a], [b], [c], [d]\}$. How many strings are in $A^4$? |
50 \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings |
48 Consider the case of $A^4$ where one of the strings in $A$ is the |
51 are in $A^4$? (2) Consider the case of $A^4$ where one of |
49 empty string, for example $A = \{[a], [b], [c], []\}$. |
52 the strings in $A$ is the empty string, for example $A = |
|
53 \{[a], [b], [c], []\}$. |
50 |
54 |
51 \item How many regular expressions are there to match the string |
55 \item How many basic regular expressions are there to match |
52 $abc$? How many if they cannot include $\epsilon$ and $\varnothing$? |
56 the string $abcd$? (ii) How many if they cannot include |
53 How many if they are also not allowed to contain stars? How many if |
57 $\epsilon$ and $\varnothing$? (iii) How many if they are |
54 they are also not allowed to contain $\_ + \_$? |
58 also not allowed to contain stars? (iv) How many if they |
|
59 are also not allowed to contain $\_ + \_$? |
55 |
60 |
56 \item When are two regular expressions equivalent? Can you think of |
61 \item When are two regular expressions equivalent? Can you |
57 instances where two regular expressions match the same strings, but |
62 think of instances where two regular expressions match |
58 it is not so obvious that they do? For example $a + b$ and $b + a$ |
63 the same strings, but it is not so obvious that they do? |
59 do not count\ldots they obviously match the same strings, namely |
64 For example $a + b$ and $b + a$ do not count\ldots they |
60 $[a]$ and $[b]$. |
65 obviously match the same strings, namely $[a]$ and |
|
66 $[b]$. |
|
67 |
61 \end{enumerate} |
68 \end{enumerate} |
62 |
69 |
63 \end{document} |
70 \end{document} |
64 |
71 |
65 %%% Local Variables: |
72 %%% Local Variables: |