23 |
23 |
24 |
24 |
25 \noindent |
25 \noindent |
26 where $\Sigma^*$ is in our case the set of all strings (what follows |
26 where $\Sigma^*$ is in our case the set of all strings (what follows |
27 also holds for any kind of ``domain'', like the set of all integers or |
27 also holds for any kind of ``domain'', like the set of all integers or |
28 set of all binary trees, etc). Let us assume $P(s)$ is a property that |
28 the set of all binary trees, etc). Let us assume $P(s)$ is a property that |
29 is about strings, for example $P(s)$ could be ``the string $s$ has |
29 is about strings, for example $P(s)$ could be ``the string $s$ has |
30 an even length'', or ``the string $s$ starts with the letter |
30 an even length'', or ``the string $s$ starts with the letter |
31 \texttt{a}''. Every such property carves out a subset of strings from |
31 \texttt{a}''. Every such property carves out a subset of strings from |
32 $\Sigma^*$, which in the picture above is depicted as a grey |
32 $\Sigma^*$, which in the picture above is depicted as a grey |
33 circle. This subset of strings is often written as a comprehension like |
33 circle. This subset of strings is often written as a comprehension like |
40 meaning all the $s$ (out of $\Sigma^*$) for which the property $P(s)$ |
40 meaning all the $s$ (out of $\Sigma^*$) for which the property $P(s)$ |
41 is true. If $P(s)$ would not be true then the corresponding string $s$ |
41 is true. If $P(s)$ would not be true then the corresponding string $s$ |
42 would be outside the grey area where $\neg P(s)$ holds. Notice that |
42 would be outside the grey area where $\neg P(s)$ holds. Notice that |
43 sometimes the property $P(s)$ holds for every string in |
43 sometimes the property $P(s)$ holds for every string in |
44 $\Sigma^*$. Then the grey area would fill out the whole rectangle and |
44 $\Sigma^*$. Then the grey area would fill out the whole rectangle and |
45 the set where $\neg P(s)$ holds is empty. Similarly, the property $P(s)$ |
45 the set where $\neg P(s)$ holds is empty. Similarly, if the property $P(s)$ |
46 holds for no string in which case the grey circle is empty. |
46 holds for no string, then the grey circle is empty. |
47 |
47 |
48 Now, we are looking for the complement of the set defined in \eqref{set}. |
48 Now, we are looking for the complement of the set defined in \eqref{set}. |
49 This complement set is often written as |
49 This complement set is often written as |
50 |
50 |
51 \[ |
51 \[ |
53 \] |
53 \] |
54 |
54 |
55 \noindent |
55 \noindent |
56 It is the area of $\Sigma^*$ which isn't grey, that is $\Sigma^*$ |
56 It is the area of $\Sigma^*$ which isn't grey, that is $\Sigma^*$ |
57 minus $\{s \in \Sigma^*\;|\; P(s) \}$, \textbf{or} written differently |
57 minus $\{s \in \Sigma^*\;|\; P(s) \}$, \textbf{or} written differently |
58 it is the set $\{s \in \Sigma^*\;|\; \neg P(s) \}$. That means it the |
58 it is the set $\{s \in \Sigma^*\;|\; \neg P(s) \}$. That means it is the |
59 set of all the strings where $\neg P(s)$ holds. Consequently we have |
59 set of all the strings where $\neg P(s)$ holds. Consequently we have |
60 for any complement set the equation: |
60 for any complement set the equation: |
61 |
61 |
62 \begin{equation}\label{eq} |
62 \begin{equation}\label{eq} |
63 \overline{\{s \in \Sigma^*\;|\; P(s) \}} = \{s \in \Sigma^*\;|\; \neg P(s) \} |
63 \overline{\{s \in \Sigma^*\;|\; P(s) \}} = \{s \in \Sigma^*\;|\; \neg P(s) \} |
64 \end{equation} |
64 \end{equation} |
65 |
65 |
66 \section*{Semantic derivative} |
66 \section*{Semantic Derivative} |
67 |
67 |
68 Our semantic derivative $Der\;c\;A$ is nothing else than a property that defines |
68 Our semantic derivative $Der\;c\;A$ is nothing else than a property that defines |
69 a subset of strings (inside $\Sigma^*$). The corresponding |
69 a subset of strings (inside $\Sigma^*$). The corresponding |
70 property $P(s)$ is $c::s \in A$ because we defined $Der\;c\;A$ as |
70 property $P(s)$ is $c::s \in A$ because we defined $Der\;c\;A$ as |
71 |
71 |
73 Der\;c\;A \;\dn\; \{s \in \Sigma^*\;|\; c::s \in A\} |
73 Der\;c\;A \;\dn\; \{s \in \Sigma^*\;|\; c::s \in A\} |
74 \] |
74 \] |
75 |
75 |
76 \noindent |
76 \noindent |
77 That means $Der\;c\;A$ is some grey area inside $\Sigma^*$. Obviously |
77 That means $Der\;c\;A$ is some grey area inside $\Sigma^*$. Obviously |
78 which subset, or grey area, we are carving out from $\Sigma^*$ depends on what we |
78 which subset, or which grey area, we are carving out from $\Sigma^*$ depends on what we |
79 choose for $c$ and $A$.\bigskip |
79 choose for $c$ and $A$.\bigskip |
80 |
80 |
81 |
81 |
82 \noindent |
82 \noindent |
83 Let us see how this pans out in a concrete example. For this let |
83 Let us see how this pans out in a concrete example. For this let |
117 \end{equation} |
117 \end{equation} |
118 |
118 |
119 \noindent |
119 \noindent |
120 This can be calculated by ``subtracting'' $\{[aa], [bb], [a]\}$ from |
120 This can be calculated by ``subtracting'' $\{[aa], [bb], [a]\}$ from |
121 $\Sigma^*$. I let you check whether I did this correctly. According |
121 $\Sigma^*$. I let you check whether I did this correctly. According |
122 to the equation in \eqref{eq} this should be equal to |
122 to the equation in \eqref{eq} this should also be equal to |
123 |
123 |
124 \[ |
124 \[ |
125 \overline{Der\;a\;A} = \{s \in \Sigma^*\;|\;a::s\not\in A\} |
125 \overline{Der\;a\;A} = \{s \in \Sigma^*\;|\;\neg(a::s\in A)\} |
126 \] |
126 \] |
127 |
127 |
128 \noindent Let us test in turn every string in $\Sigma^*$ and see |
128 \noindent Let us test in turn every string in $\Sigma^*$ and see |
129 whether $a::s$ is in $A$ which we set above to |
129 whether $a::s$ is in $A$ which we set above to |
130 |
130 |
131 \[\{[aaa], [abb], [aa], [bb], []\}\] |
131 \[\{[aaa], [abb], [aa], [bb], []\}\] |
132 |
132 |
133 \noindent |
133 \noindent |
134 This gives rise to the following table where in the first column are |
134 This gives rise to the following table where in the first column are all |
135 the strings of $\Sigma^*$ and in the second whether $a::s \in A$ holds. The third column |
135 the strings of $\Sigma^*$ and in the second whether $a::s \in A$ holds. The third column |
136 is the negated version of the second. |
136 is the negated version of the second, namely $\neg(a::s\in A)$ which is the same as |
|
137 $a::s\not\in A$. |
137 |
138 |
138 \begin{center} |
139 \begin{center} |
139 \begin{tabular}{r|c|l} |
140 \begin{tabular}{r|c|l} |
140 s & is $a::s \in A$? & $\neg(a::s \in A) \Leftrightarrow a::s \not\in A$\\ |
141 $s\in\Sigma^*$ & is $a::s \in A$? & $\neg(a::s \in A) \Leftrightarrow a::s \not\in A$\\ |
141 \hline |
142 \hline |
142 $[]$ & no & yes\\ |
143 $[]$ & no & yes\\ |
143 $[a]$ & yes& no\\ |
144 $[a]$ & yes& no\\ |
144 $[b]$ & no & yes\\ |
145 $[b]$ & no & yes\\ |
145 $[aa]$ & yes& no\\ |
146 $[aa]$ & yes& no\\ |
156 $[bbb]$ & no & yes\\ |
157 $[bbb]$ & no & yes\\ |
157 \end{tabular} |
158 \end{tabular} |
158 \end{center} |
159 \end{center} |
159 |
160 |
160 \noindent |
161 \noindent |
161 Collecting all the yes in the third row gives you the set in \eqref{Der}. So it works out in this example. |
162 Collecting all the yes in the third column gives you the set in |
|
163 \eqref{Der}. So it works out in this example. The idea is that this always works out. ;o) |
|
164 \bigskip |
|
165 |
|
166 \noindent |
|
167 BTW, notice that all three properties are the same |
|
168 |
|
169 \[ |
|
170 \neg(a::s \in A) \quad\Leftrightarrow\quad a::s \not\in A |
|
171 \quad\Leftrightarrow\quad a::s \in \overline{A} |
|
172 \] |
|
173 |
|
174 \noindent |
|
175 This means we have |
|
176 |
|
177 \begin{equation}\label{D} |
|
178 \overline{Der\;a\;A} = Der\;a\;\overline{A} |
|
179 \end{equation} |
|
180 |
|
181 \noindent |
|
182 I let you check whether this makes sense. |
|
183 |
|
184 \section*{Not-Regular Expression} |
|
185 |
|
186 With the equation in \eqref{D} we can also very quickly verify that the |
|
187 $der$-definition for the not-regular expression satisfies the property |
|
188 of derivatives, namely |
|
189 |
|
190 \begin{equation}\label{derprop} |
|
191 \forall c\,r.\;\;\;L(der\;c\;r) = Der\;c\;(L(r)) |
|
192 \end{equation} |
|
193 |
|
194 \noindent |
|
195 holds. We defined the language of a not-regular expression as |
|
196 |
|
197 \[ |
|
198 L(\sim r) \;\dn\; \Sigma^* - L(r) |
|
199 \] |
|
200 |
|
201 \noindent |
|
202 Using the overline notation, maybe I should have defined this equivalently as |
|
203 |
|
204 \[ |
|
205 L(\sim r) \;\dn\; \overline{L(r)} |
|
206 \] |
|
207 |
|
208 \noindent |
|
209 meaning all the strings that $r$ \emph{cannot} match. We defined the derivative for |
|
210 the not-regular expression as |
|
211 |
|
212 \[ |
|
213 der\;c\;(\sim r) \;\dn\; \sim(der\;c\;r) |
|
214 \] |
|
215 |
|
216 \noindent |
|
217 The big question is now does this definition satisfy the property in |
|
218 \eqref{derprop}? Lets see: We would have to prove this by induction on regular |
|
219 expressions. When we are in the case for $\sim r$ the reasoning is as follows: |
|
220 |
|
221 \begin{center} |
|
222 \def\arraystretch{1.5} |
|
223 \begin{tabular}{llll} |
|
224 $L(der\;c\;(\sim r))$ & $\dn$ & $L(\sim (der\;c\;r))$ & by definition of $der$\\ |
|
225 & $\dn$ & $\overline{L(der\;c\;r)}$ & by definition of $L$\\ |
|
226 & $=$ & $\overline{Der\;c\;(L(r))}$ & by IH\\ |
|
227 & $=$ & $Der\;c\;\overline{(L(r))}$ & by \eqref{D}\\ |
|
228 & $\dn$ & $Der\;c\;(L(\sim r))$ & by definition of $L$\\ |
|
229 \end{tabular} |
|
230 \end{center} |
|
231 |
|
232 \noindent |
|
233 That means we have established the property of derivatives in the $\sim r$-case\dots{}yippee~;o) |
162 |
234 |
163 \end{document} |
235 \end{document} |
164 |
236 |
165 %%% Local Variables: |
237 %%% Local Variables: |
166 %%% mode: latex |
238 %%% mode: latex |