37 |
37 |
38 \noindent In case an equation is true, give an |
38 \noindent In case an equation is true, give an |
39 explanation; otherwise give a counter-example. |
39 explanation; otherwise give a counter-example. |
40 |
40 |
41 \solution{1 + 3 are equal; 2 + 4 are not. Interesting is 4 where |
41 \solution{1 + 3 are equal; 2 + 4 are not. Interesting is 4 where |
42 $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$\medskip |
42 $A = \{[a]\}$, $B = \{[]\}$ and $C = \{[a], []\}$ is an |
43 |
43 counter-example.\medskip |
44 For equations like 3 it is always a god idea to prove the |
44 |
|
45 For equations like 3 it is always a good idea to prove the |
45 two inclusions |
46 two inclusions |
46 |
47 |
47 \[ |
48 \[ |
48 A^* \subseteq A^* @ A^* \qquad |
49 A^* \subseteq A^* @ A^* \qquad |
49 A^* @ A^* \subseteq A^* |
50 A^* @ A^* \subseteq A^* |
125 equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot |
126 equivalent $(\ONE + a)^* \equiv^? a^*$ and $(a \cdot |
126 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
127 b)^* \cdot a \equiv^? a \cdot (b \cdot a)^*$. |
127 |
128 |
128 \solution{Both are equivalent, but why the second? Essentially you have to show that each string in one set is in the other. For 2 this means you can do an induction proof that $(ab)^na$ is the same string as $a(ba)^n$, where the former is in the first set and the latter in the second.} |
129 \solution{Both are equivalent, but why the second? Essentially you have to show that each string in one set is in the other. For 2 this means you can do an induction proof that $(ab)^na$ is the same string as $a(ba)^n$, where the former is in the first set and the latter in the second.} |
129 |
130 |
|
131 |
|
132 \item Give an argument for why the following holds: |
|
133 if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$. |
|
134 |
|
135 \solution{ This requires an inductive proof. There are a number of |
|
136 ways to prove this. It is clear that if $s \in L (r^{\{n\}})$ then |
|
137 also $s \in L (r^{\{..n\}})$. |
|
138 |
|
139 So one way to prove this is to show |
|
140 that if $s \in L (r^{\{..n\}})$ then also $s \in L (r^{\{n\}})$ |
|
141 (under the assumption that $r$ is nullable, otherwise it would not |
|
142 be true). The assumption $s \in L (r^{\{..n\}})$ means |
|
143 that $s \in L(r^{\{i\}})$ with $i \leq n$ holds |
|
144 and we have to show that $s \in L(r^{\{n\}})$ holds. |
|
145 |
|
146 One can do this by induction for languages as follows: |
|
147 |
|
148 \[ |
|
149 \textit{if}\; [] \in A \;\textit{and}\; s \in A^n |
|
150 \;\textit{then}\; s \in A^{n+m} |
|
151 \] |
|
152 |
|
153 The proof is by induction on $m$. The base case $m=0$ is trivial. |
|
154 For the $m + 1$ case we have the induction hypothesis: |
|
155 |
|
156 \[ |
|
157 \textit{if}\; [] \in A \;\textit{and}\; s \in A^n |
|
158 \;\textit{then}\; s \in A^{n+m} |
|
159 \] |
|
160 |
|
161 and we have to show |
|
162 |
|
163 \[ |
|
164 s \in A^{n+m+1} |
|
165 \] |
|
166 |
|
167 under the assumption $[] \in A$ and $s \in A^n$. From the |
|
168 assumptions and the IH we can infer that $s\in A^{n + m}$. |
|
169 Then using the assumption $[] \in A$ we can infer that also |
|
170 |
|
171 \[ |
|
172 s\in A \,@\, A^{n + m} |
|
173 \] |
|
174 |
|
175 which is equivalent to what we need to show $s \in A^{n+m+1}$. |
|
176 |
|
177 Now we know $s \in L(r^{\{i\}})$ with $i \leq n$. Since $i + m = n$ |
|
178 for some $m$ we can conclude that $s \in L(r^{\{n\}})$. Done. |
|
179 |
|
180 } |
|
181 |
130 \item Given the regular expression $r = (a \cdot b + b)^*$. |
182 \item Given the regular expression $r = (a \cdot b + b)^*$. |
131 Compute what the derivative of $r$ is with respect to |
183 Compute what the derivative of $r$ is with respect to |
132 $a$, $b$ and $c$. Is $r$ nullable? |
184 $a$, $b$ and $c$. Is $r$ nullable? |
133 |
|
134 \item Give an argument for why the following holds: |
|
135 if $r$ is nullable then $r^{\{n\}} \equiv r^{\{..n\}}$. |
|
136 |
|
137 \solution{This was from last week; I just explicitly added it here.} |
|
138 |
185 |
139 \item Define what is meant by the derivative of a regular |
186 \item Define what is meant by the derivative of a regular |
140 expressions with respect to a character. (Hint: The |
187 expressions with respect to a character. (Hint: The |
141 derivative is defined recursively.) |
188 derivative is defined recursively.) |
142 |
189 |
143 \solution{the recursive function for $der$} |
190 \solution{The recursive function for $der$.} |
144 |
191 |
145 \item Assume the set $Der$ is defined as |
192 \item Assume the set $Der$ is defined as |
146 |
193 |
147 \begin{center} |
194 \begin{center} |
148 $Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ |
195 $Der\,c\,A \dn \{ s \;|\; c\!::\!s \in A\}$ |
233 \[(aa|bb|(ab|ba)\cdot (aa|bb)^* \cdot (ba|ab))^* \cdot (b|(ab|ba)(bb|aa)^* \cdot a) |
280 \[(aa|bb|(ab|ba)\cdot (aa|bb)^* \cdot (ba|ab))^* \cdot (b|(ab|ba)(bb|aa)^* \cdot a) |
234 \] |
281 \] |
235 |
282 |
236 (copied from somewhere ;o) |
283 (copied from somewhere ;o) |
237 |
284 |
238 The idea behind it is essentially the DFA |
285 The idea behind this monstrous regex is essentially the DFA |
239 |
286 |
240 \begin{center} |
287 \begin{center} |
241 \begin{tikzpicture}[scale=1,>=stealth',very thick, |
288 \begin{tikzpicture}[scale=1,>=stealth',very thick, |
242 every state/.style={minimum size=0pt, |
289 every state/.style={minimum size=0pt, |
243 draw=blue!50,very thick,fill=blue!20}] |
290 draw=blue!50,very thick,fill=blue!20}] |