|
1 \documentclass{article} |
|
2 \usepackage{../style} |
|
3 \usepackage{../graphics} |
|
4 |
|
5 \begin{document} |
|
6 |
|
7 \section*{Complement Sets} |
|
8 |
|
9 Consider the following picture: |
|
10 |
|
11 \begin{center} |
|
12 \begin{tikzpicture}[fill=gray] |
|
13 % left hand |
|
14 \scope |
|
15 \fill (0,0) circle (1); |
|
16 \endscope |
|
17 % outline |
|
18 \draw (0,0) circle (1) (0,1) node [text=white,below] {$P(s)$} |
|
19 (2,0) node [text=black,above] {$\neg P(s)$} |
|
20 (-2,-2) rectangle (3,2) node [text=black,above] {$\Sigma^*$}; |
|
21 \end{tikzpicture} |
|
22 \end{center} |
|
23 |
|
24 |
|
25 \noindent |
|
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 |
|
28 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 |
|
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 |
|
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 |
|
34 |
|
35 \begin{equation}\label{set} |
|
36 \{s \in \Sigma^*\;|\; P(s) \} |
|
37 \end{equation} |
|
38 |
|
39 \noindent |
|
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$ |
|
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 |
|
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)$ |
|
46 holds for no string in which case the grey circle is empty. |
|
47 |
|
48 Now, we are looking for the complement of the set defined in \eqref{set}. |
|
49 This complement set is often written as |
|
50 |
|
51 \[ |
|
52 \overline{\{s \in \Sigma^*\;|\; P(s) \}} |
|
53 \] |
|
54 |
|
55 \noindent |
|
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 |
|
58 it is the set $\{s \in \Sigma^*\;|\; \neg P(s) \}$. That means it the |
|
59 set of all the strings where $\neg P(s)$ holds. Consequently we have |
|
60 for any complement set the equation: |
|
61 |
|
62 \begin{equation}\label{eq} |
|
63 \overline{\{s \in \Sigma^*\;|\; P(s) \}} = \{s \in \Sigma^*\;|\; \neg P(s) \} |
|
64 \end{equation} |
|
65 |
|
66 \section*{Semantic derivative} |
|
67 |
|
68 Our semantic derivative $Der\;c\;A$ is nothing else than a property that defines |
|
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 |
|
71 |
|
72 \[ |
|
73 Der\;c\;A \;\dn\; \{s \in \Sigma^*\;|\; c::s \in A\} |
|
74 \] |
|
75 |
|
76 \noindent |
|
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 |
|
79 choose for $c$ and $A$.\bigskip |
|
80 |
|
81 |
|
82 \noindent |
|
83 Let us see how this pans out in a concrete example. For this let |
|
84 $\Sigma^*$ not be the set of all strings, but only the set of strings |
|
85 upto a length of 3 over the alphabet $\{a, b\}$. That means $\Sigma^*$ |
|
86 (or the rectangle in the picture above) consists of the strings |
|
87 |
|
88 \[ |
|
89 \Sigma^* = \left\{\begin{array}{l} |
|
90 $\ensuremath{[]}$\\ |
|
91 $\ensuremath{[a], [b]}$\\ |
|
92 $\ensuremath{[aa], [ab], [ba], [bb]}$\\ |
|
93 $\ensuremath{[aaa], [aab], [aba], [abb], [baa], [bab], [bba], [bbb]}$ |
|
94 \end{array}\right\} |
|
95 \] |
|
96 |
|
97 |
|
98 \noindent |
|
99 If we set $A$ to $\{[aaa], [abb], [aa], [bb], []\}$, then $Der\;a\;A$ is the subset |
|
100 |
|
101 \[ |
|
102 Der\;a\;A = \{[aa], [bb], [a]\} |
|
103 \] |
|
104 |
|
105 \noindent |
|
106 which is given by the definition of |
|
107 $Der\;a\;A \dn \{s \in \Sigma^*\;|\;a::s\in A\}$. Now lets look at what |
|
108 the complement of this set looks like: |
|
109 |
|
110 \begin{equation}\label{Der} |
|
111 \overline{Der\;a\;A} = \left\{\begin{array}{l} |
|
112 $\ensuremath{[]}$\\ |
|
113 $\ensuremath{[b]}$\\ |
|
114 $\ensuremath{[ab], [ba]}$\\ |
|
115 $\ensuremath{[aaa], [aab], [aba], [abb], [baa], [bab], [bba], [bbb]}$ |
|
116 \end{array}\right\} |
|
117 \end{equation} |
|
118 |
|
119 \noindent |
|
120 This can be calculated by ``subtracting'' $\{[aa], [bb], [a]\}$ from |
|
121 $\Sigma^*$. I let you check whether I did this correctly. According |
|
122 to the equation in \eqref{eq} this should be equal to |
|
123 |
|
124 \[ |
|
125 \overline{Der\;a\;A} = \{s \in \Sigma^*\;|\;a::s\not\in A\} |
|
126 \] |
|
127 |
|
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 |
|
130 |
|
131 \[\{[aaa], [abb], [aa], [bb], []\}\] |
|
132 |
|
133 \noindent |
|
134 This gives rise to the following table where in the first column are |
|
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. |
|
137 |
|
138 \begin{center} |
|
139 \begin{tabular}{r|c|l} |
|
140 s & is $a::s \in A$? & $\neg(a::s \in A) \Leftrightarrow a::s \not\in A$\\ |
|
141 \hline |
|
142 $[]$ & no & yes\\ |
|
143 $[a]$ & yes& no\\ |
|
144 $[b]$ & no & yes\\ |
|
145 $[aa]$ & yes& no\\ |
|
146 $[ab]$ & no & yes\\ |
|
147 $[ba]$ & no & yes\\ |
|
148 $[bb]$ & yes& no\\ |
|
149 $[aaa]$ & no & yes\\ |
|
150 $[aab]$ & no & yes\\ |
|
151 $[aba]$ & no & yes\\ |
|
152 $[abb]$ & no & yes\\ |
|
153 $[baa]$ & no & yes\\ |
|
154 $[bab]$ & no & yes\\ |
|
155 $[bba]$ & no & yes\\ |
|
156 $[bbb]$ & no & yes\\ |
|
157 \end{tabular} |
|
158 \end{center} |
|
159 |
|
160 \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 |
|
163 \end{document} |
|
164 |
|
165 %%% Local Variables: |
|
166 %%% mode: latex |
|
167 %%% TeX-master: t |
|
168 %%% End: |