23 recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case |
33 recognise the strings (for 1) $ab$ and (for 2) $aaa$. Give in each case |
24 \emph{all} the values and indicate which one is the POSIX value. |
34 \emph{all} the values and indicate which one is the POSIX value. |
25 |
35 |
26 |
36 |
27 \item If a regular expression $r$ does not contain any occurrence of $\ZERO$, |
37 \item If a regular expression $r$ does not contain any occurrence of $\ZERO$, |
28 is it possible for $L(r)$ to be empty? Explain why, or give a proof. |
38 is it possible for $L(r)$ to be empty? Explain why, or give a proof. |
|
39 |
|
40 \solution{ |
|
41 The property to prove is |
|
42 |
|
43 \begin{center} |
|
44 $P(r)$: If $r$ does not contain $\ZERO$, then $L(r) \not= \emptyset$. |
|
45 \end{center} |
|
46 |
|
47 For this you have to now go through all cases. |
|
48 |
|
49 Case $r = 0$: $P(\ZERO)$ says: If $\ZERO$ does not contain $\ZERO$ |
|
50 then \ldots. The premise is obviously false, so everything follows, |
|
51 in particular $L(r) \not= \emptyset$.\medskip |
|
52 |
|
53 Case $r = \ONE$ and $r = c$ are similar, just that the premise is |
|
54 true, but also $L(\ONE)$ and $L(c)$ are not empty. So we shown |
|
55 $L(r) \not= \emptyset$.\medskip |
|
56 |
|
57 Case $r = r_1 + r_2$: We know $P(r_1)$ and $P(r_2)$ as IHs. We need to show |
|
58 $P(r_1 + r_2)$: If $r_1 + r_2$ does not contain $\ZERO$, then $L(r_1 + r_2) \not= \emptyset$. |
|
59 |
|
60 If $r_1 + r_2$ does not contain $\ZERO$, then also $r_1$ does not contain $\ZERO$ |
|
61 and $r_2$ does not contain $\ZERO$. So we can apply the two IHs $P(r_1)$ and $P(r_2)$, |
|
62 which allow us to infer that $L(r_1) \not= \emptyset$ and $L(r_2) \not= \emptyset$. |
|
63 But if this is the case, then also $L(r_1 + r_2) \not= \emptyset$, which is what we needed |
|
64 to show in this case.\medskip |
|
65 |
|
66 The other cases are similar.\bigskip |
|
67 |
|
68 |
|
69 This lemma essentially says that for basic regular expressions, if |
|
70 they do not match anything at all, they must contain $\ZERO$(s) |
|
71 somewhere. |
|
72 |
|
73 } |
29 |
74 |
30 \item Define the tokens and regular expressions for a language |
75 \item Define the tokens and regular expressions for a language |
31 consisting of numbers, left-parenthesis $($, right-parenthesis $)$, |
76 consisting of numbers, left-parenthesis $($, right-parenthesis $)$, |
32 identifiers and the operations $+$, $-$ and $*$. Can the following |
77 identifiers and the operations $+$, $-$ and $*$. Can the following |
33 strings in this language be lexed? |
78 strings in this language be lexed? |
44 \item Assume $r$ is nullable. Show that |
89 \item Assume $r$ is nullable. Show that |
45 \[ 1 + r + r\cdot r \;\equiv\; r\cdot r |
90 \[ 1 + r + r\cdot r \;\equiv\; r\cdot r |
46 \] |
91 \] |
47 |
92 |
48 holds. |
93 holds. |
|
94 |
|
95 \solution{ |
|
96 If $r$ is nullable, then $1 + r \equiv r$. With this you can replace |
|
97 |
|
98 \begin{align} |
|
99 (1 + r) + r\cdot r & \equiv r + r\cdot r\\ |
|
100 & \equiv r \cdot (1 + r)\\ |
|
101 & \equiv r \cdot r |
|
102 \end{align} |
|
103 |
|
104 where in (2) you pull out the ``factor'' $r$ (because $r_1 \cdot (r_2 + r_3) \equiv r_1 \cdot r_2 + r_1 \cdot r_3$). |
|
105 } |
|
106 |
49 |
107 |
50 \item \textbf{(Deleted)} Assume that $s^{-1}$ stands for the operation of reversing a |
108 \item \textbf{(Deleted)} Assume that $s^{-1}$ stands for the operation of reversing a |
51 string $s$. Given the following \emph{reversing} function on regular |
109 string $s$. Given the following \emph{reversing} function on regular |
52 expressions |
110 expressions |
53 |
111 |
124 \textit{atmostempty} (for regular expressions that match no |
182 \textit{atmostempty} (for regular expressions that match no |
125 string or only the empty string), \textit{somechars} (for |
183 string or only the empty string), \textit{somechars} (for |
126 regular expressions that match some non-empty string), |
184 regular expressions that match some non-empty string), |
127 \textit{infinitestrings} (for regular expressions that can match |
185 \textit{infinitestrings} (for regular expressions that can match |
128 infinitely many strings). |
186 infinitely many strings). |
|
187 |
|
188 \solution{ |
|
189 \textbf{zeroable}: The property is $z(r) \;\text{iff}\; L(r) = \emptyset$: |
|
190 |
|
191 \begin{align} |
|
192 z(\ZERO) &\dn true\\ |
|
193 z(\ONE) &\dn false\\ |
|
194 z(c) &\dn false\\ |
|
195 z(r_1 + r_2) &\dn z(r_1) \wedge z(r_2)\\ |
|
196 z(r_1 \cdot r_2) &\dn z(r_1) \vee z(r_2)\\ |
|
197 z(r^*) &\dn false |
|
198 \end{align}\bigskip |
|
199 |
|
200 \textbf{atmostempty}: The property is ``either $L(r) = \emptyset$ or $L(r) = \{[]\}$'', which |
|
201 is more formally $a(r) \;\text{iff}\; L(r) \subseteq \{[]\}$: |
|
202 |
|
203 \begin{align} |
|
204 a(\ZERO) &\dn true\\ |
|
205 a(\ONE) &\dn true\\ |
|
206 a(c) &\dn false\\ |
|
207 a(r_1 + r_2) &\dn a(r_1) \wedge a(r_2)\\ |
|
208 a(r_1 \cdot r_2) &\dn z(r_1) \vee z(r_2) \vee (a(r_1) \wedge a(r_2))\\ |
|
209 a(r^*) &\dn a(r) |
|
210 \end{align} |
|
211 |
|
212 For this it is good to remember the regex should either not |
|
213 match anything at all, or just the empty string.\bigskip |
|
214 |
|
215 \textbf{somechars}: The property is ``$L(r)$ must contain a string which is not the empty string'', which |
|
216 is more formally $s(r) \;\text{iff}\; \exists\,s. s \not= [] \wedge s \in L(r)$: |
|
217 |
|
218 \begin{align} |
|
219 s(\ZERO) &\dn false\\ |
|
220 s(\ONE) &\dn false\\ |
|
221 s(c) &\dn true\\ |
|
222 s(r_1 + r_2) &\dn s(r_1) \vee s(r_2)\\ |
|
223 s(r_1 \cdot r_2) &\dn (\neg z(r_1) \wedge s(r_2)) \;\vee\; (\neg z(r_2) \wedge s(r_1))\\ |
|
224 s(r^*) &\dn s(r) |
|
225 \end{align} |
|
226 |
|
227 Here the interesting case is $r_1 \cdot r_2$ where one essentially has to make sure |
|
228 that one of the regexes is not zeroable, because then the resulting regex cannot match any |
|
229 string.\bigskip |
|
230 |
|
231 \textbf{infinitestrings}: The property is |
|
232 $i(r) \;\text{iff}\; L(r)\;\text{is infinite}$: |
|
233 |
|
234 \begin{align} |
|
235 i(\ZERO) &\dn false\\ |
|
236 i(\ONE) &\dn false\\ |
|
237 i(c) &\dn false\\ |
|
238 i(r_1 + r_2) &\dn i(r_1) \vee i(r_2)\\ |
|
239 i(r_1 \cdot r_2) &\dn (\neg z(r_1) \wedge i(r_2)) \;\vee\; (\neg z(r_2) \wedge i(r_1))\\ |
|
240 i(r^*) &\dn \neg a(r) |
|
241 \end{align} |
|
242 |
|
243 Here the interesting bit is that as soon $r$ can match at least a single string, then $r^*$ |
|
244 will match infinitely many strings. |
|
245 } |
|
246 |
129 |
247 |
130 \item There are two kinds of automata that are generated for |
248 \item There are two kinds of automata that are generated for |
131 regular expression matching---DFAs and NFAs. (1) Regular expression engines like |
249 regular expression matching---DFAs and NFAs. (1) Regular expression engines like |
132 the one in Python generate NFAs. Explain what is the problem with such |
250 the one in Python generate NFAs. Explain what is the problem with such |
133 NFAs and what is the reason why they use NFAs. (2) Regular expression |
251 NFAs and what is the reason why they use NFAs. (2) Regular expression |