45 \item Read the handout of the first lecture and the handout |
50 \item Read the handout of the first lecture and the handout |
46 about notation. Make sure you understand the concepts of |
51 about notation. Make sure you understand the concepts of |
47 strings and languages. In the context of the CFL-course, |
52 strings and languages. In the context of the CFL-course, |
48 what is meant by the term \emph{language}? |
53 what is meant by the term \emph{language}? |
49 |
54 |
|
55 \solution{A language - in this context - is just a set of |
|
56 strings. Some of these sets can actually not be described by |
|
57 regular expressions. Only regular​ languages can. This is |
|
58 something for lecture 3.} |
|
59 |
50 \item Give the definition for regular expressions---this is an |
60 \item Give the definition for regular expressions---this is an |
51 inductive datatype. What is the |
61 inductive datatype. What is the |
52 meaning of a regular expression? (Hint: The meaning is |
62 meaning of a regular expression? (Hint: The meaning is |
53 defined recursively.) |
63 defined recursively.) |
|
64 |
|
65 \solution{Here I would also expect the grammar for basic regular |
|
66 expressions and the definition of the recursive L-function. Discuss |
|
67 differences between $r_1 + r_2$ and $r^+$. Discuss differences between |
|
68 ``real-life regexes'' and regexes in this module.} |
54 |
69 |
55 \item Assume the concatenation operation of two strings is |
70 \item Assume the concatenation operation of two strings is |
56 written as $s_1 @ s_2$. Define the operation of |
71 written as $s_1 @ s_2$. Define the operation of |
57 \emph{concatenating} two sets of strings. This operation |
72 \emph{concatenating} two sets of strings. This operation |
58 is also written as $\_ \,@\, \_$. According to |
73 is also written as $\_ \,@\, \_$. According to |
59 this definition, what is $A \,@\, \{\}$ equal to? |
74 this definition, what is $A \,@\, \{\}$ equal to? |
60 Is in general $A\,@\,B$ equal to $B\,@\,A$? |
75 Is in general $A\,@\,B$ equal to $B\,@\,A$? |
61 |
76 |
|
77 \solution{ What is $A @ {[]}$? Are there special cases |
|
78 where $A @ B = B @ A$? } |
|
79 |
62 \item Assume a set $A$ contains 4 strings and a set $B$ |
80 \item Assume a set $A$ contains 4 strings and a set $B$ |
63 contains 7 strings. None of the strings is the empty |
81 contains 7 strings. None of the strings is the empty |
64 string. How many strings are in $A \,@\, B$? |
82 string. How many strings are in $A \,@\, B$? |
65 |
83 |
|
84 \solution{28, but there are corner cases where there are fewer |
|
85 than 28 elements. Can students think of such corner cases? |
|
86 For example $A = \{a, ab, \ldots\}$, $B = \{bc, c,\ldots\}$ } |
|
87 |
66 \item How is the power of a language defined? (Hint: There are two |
88 \item How is the power of a language defined? (Hint: There are two |
67 rules, one for $\_^0$ and one for $\_^{n+1}$.) |
89 rules, one for $\_^0$ and one for $\_^{n+1}$.) |
|
90 |
|
91 \solution{Two rules: 0-case and n+1 case.} |
68 |
92 |
69 \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings |
93 \item Let $A = \{[a], [b], [c], [d]\}$. (1) How many strings |
70 are in $A^4$? (2) Consider also the case of $A^4$ where one of |
94 are in $A^4$? (2) Consider also the case of $A^4$ where one of |
71 the strings in $A$ is the empty string, for example $A = |
95 the strings in $A$ is the empty string, for example $A = |
72 \{[a], [b], [c], []\}$. |
96 \{[a], [b], [c], []\}$. |
|
97 |
|
98 \solution{121 is correct. But make sure you understand why it is 121 |
|
99 in cases you do not have a computer at your fingertips.} |
73 |
100 |
74 \item (1) How many basic regular expressions are there to match |
101 \item (1) How many basic regular expressions are there to match |
75 \textbf{only} the string $abcd$? (2) How many if they cannot include |
102 \textbf{only} the string $abcd$? (2) How many if they cannot include |
76 $\ONE$ and $\ZERO$? (3) How many if they are also not |
103 $\ONE$ and $\ZERO$? (3) How many if they are also not |
77 allowed to contain stars? (4) How many if they are also |
104 allowed to contain stars? (4) How many if they are also |
78 not allowed to contain $\_ + \_$? |
105 not allowed to contain $\_ + \_$? |
79 |
106 |
|
107 \solution{1-3 are infinite (tell the idea why - examples); 4 is five - remember regexes are trees.} |
|
108 |
80 \item When are two regular expressions equivalent? Can you |
109 \item When are two regular expressions equivalent? Can you |
81 think of instances where two regular expressions match |
110 think of instances where two regular expressions match |
82 the same strings, but it is not so obvious that they do? |
111 the same strings, but it is not so obvious that they do? |
83 For example $a + b$ and $b + a$ do not count\ldots they |
112 For example $a + b$ and $b + a$ do not count\ldots they |
84 obviously match the same strings, namely $[a]$ and |
113 obviously match the same strings, namely $[a]$ and |
85 $[b]$. |
114 $[b]$. |
86 |
115 |
|
116 \solution{for example $r^* = 1 + r \cdot r^*$ for any regular expression $r$. |
|
117 Can students think about why this is the case?} |
|
118 |
87 \item What is meant by the notions \emph{evil regular expressions} |
119 \item What is meant by the notions \emph{evil regular expressions} |
88 and by \emph{catastrophic backtracking}? |
120 and by \emph{catastrophic backtracking}? |
|
121 |
|
122 \solution{catastrophic backtracking also applies to other regexes, not just $(a^*)^*b$} |
89 |
123 |
90 \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$, |
124 \item Given the regular expression $(a + b)^* \cdot b \cdot (a + b)^*$, |
91 which of the following regular expressions are equivalent |
125 which of the following regular expressions are equivalent |
92 |
126 |
93 \begin{center} |
127 \begin{center} |