equal
deleted
inserted
replaced
1 \documentclass{article} |
1 \documentclass{article} |
2 \usepackage{../style} |
2 \usepackage{../style} |
3 \usepackage{../graphics} |
3 \usepackage{../graphics} |
4 |
4 |
|
5 \title{Derivative for the NOT-Regular Expression} |
|
6 |
5 \begin{document} |
7 \begin{document} |
|
8 \maketitle |
|
9 \begin{abstract} |
|
10 \noindent |
|
11 This short note explains why the derivative for the NOT-regular |
|
12 expression is defined as |
|
13 \[ |
|
14 der\,c(\sim r) \;\dn\; \sim (der\,c\,r) |
|
15 \] |
|
16 The explanation goes via complement sets, the semantic derivative (\textit{Der}) |
|
17 and how the derivative relates to the semantic derivative. |
|
18 \end{abstract} |
6 |
19 |
7 \section*{Complement Sets} |
20 \section*{Complement Sets} |
8 |
21 |
9 Consider the following picture: |
22 To start with, consider the following picture: |
10 |
23 |
11 \begin{center} |
24 \begin{center} |
12 \begin{tikzpicture}[fill=gray] |
25 \begin{tikzpicture}[fill=gray] |
13 % left hand |
26 % left hand |
14 \scope |
27 \scope |
21 \end{tikzpicture} |
34 \end{tikzpicture} |
22 \end{center} |
35 \end{center} |
23 |
36 |
24 |
37 |
25 \noindent |
38 \noindent |
26 where $\Sigma^*$ is in our case the set of all strings (what follows |
39 where $\Sigma^*$ is in our case the set of all strings (what follows in this section |
27 also holds for any kind of ``domain'', like the set of all integers or |
40 also holds for any kind of ``domain'', like the set of all integers or |
28 the set of all binary trees, etc). Let us assume $P(s)$ is a property that |
41 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 |
42 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 |
43 an even length'', or ``the string $s$ starts with the letter |
31 \texttt{a}''. Every such property carves out a subset of strings from |
44 \texttt{a}''. Every such property carves out a subset of strings from |
229 \end{tabular} |
242 \end{tabular} |
230 \end{center} |
243 \end{center} |
231 |
244 |
232 \noindent |
245 \noindent |
233 That means we have established the property of derivatives in the $\sim r$-case\dots{}yippee~;o) |
246 That means we have established the property of derivatives in the $\sim r$-case\dots{}yippee~;o) |
234 |
247 \medskip |
|
248 |
|
249 \noindent |
|
250 The conclusion is: if we want the property $L(der\,c\,r) = Der\,c\,(L(r))$ to hold and the |
|
251 semantics of $\sim r$ is defined as $\overline{L(r)}$, then the definition for the derivative |
|
252 for the NOT-regular expression must be: |
|
253 \[ |
|
254 der\,c(\sim r) \;\dn\; \sim (der\,c\,r) |
|
255 \] |
235 \end{document} |
256 \end{document} |
236 |
257 |
237 %%% Local Variables: |
258 %%% Local Variables: |
238 %%% mode: latex |
259 %%% mode: latex |
239 %%% TeX-master: t |
260 %%% TeX-master: t |