\documentclass{article}
\usepackage{../style}
\usepackage{../graphics}

\begin{document}

\section*{Complement Sets}

Consider the following picture:

\begin{center}
\begin{tikzpicture}[fill=gray]
% left hand
\scope
\fill (0,0) circle (1);
\endscope
% outline
\draw (0,0) circle (1) (0,1)  node [text=white,below] {$P(s)$}
      (2,0) node [text=black,above] {$\neg P(s)$}
      (-2,-2) rectangle (3,2) node [text=black,above] {$\Sigma^*$};
\end{tikzpicture}
\end{center}


\noindent
where $\Sigma^*$ is in our case the set of all strings (what follows
also holds for any kind of ``domain'', like the set of all integers or
set of all binary trees, etc). Let us assume $P(s)$ is a property that
is about strings, for example $P(s)$ could be ``the string $s$ has
an even length'', or ``the string $s$ starts with the letter
\texttt{a}''. Every such property carves out a subset of strings from
$\Sigma^*$, which in the picture above is depicted as a grey
circle. This subset of strings is often written as a comprehension like

\begin{equation}\label{set}
\{s \in \Sigma^*\;|\; P(s) \}
\end{equation}

\noindent
meaning all the $s$ (out of $\Sigma^*$) for which the property $P(s)$
is true. If $P(s)$ would not be true then the corresponding string $s$
would be outside the grey area where $\neg P(s)$ holds. Notice that
sometimes the property $P(s)$ holds for every string in
$\Sigma^*$. Then the grey area would fill out the whole rectangle and
the set where $\neg P(s)$ holds is empty. Similarly, the property $P(s)$
holds for no string in which case the grey circle is empty.

Now, we are looking for the complement of the set defined in \eqref{set}.
This complement set is often written as

\[
\overline{\{s \in \Sigma^*\;|\; P(s) \}}
\]

\noindent
It is the area of $\Sigma^*$ which isn't grey, that is $\Sigma^*$
minus $\{s \in \Sigma^*\;|\; P(s) \}$, \textbf{or} written differently
it is the set $\{s \in \Sigma^*\;|\; \neg P(s) \}$. That means it the
set of all the strings where $\neg P(s)$ holds. Consequently we have
for any complement set the equation:

\begin{equation}\label{eq}
\overline{\{s \in \Sigma^*\;|\; P(s) \}} = \{s \in \Sigma^*\;|\; \neg P(s) \}
\end{equation}

\section*{Semantic derivative}

Our semantic derivative $Der\;c\;A$ is nothing else than a property that defines
a subset of strings (inside $\Sigma^*$). The corresponding
property $P(s)$ is $c::s \in A$ because we defined $Der\;c\;A$ as

\[
Der\;c\;A \;\dn\; \{s \in \Sigma^*\;|\; c::s \in A\}
\]

\noindent
That means $Der\;c\;A$ is some grey area inside $\Sigma^*$. Obviously
which subset, or grey area, we are carving out from $\Sigma^*$ depends on what we
choose for $c$ and $A$.\bigskip


\noindent
Let us see how this pans out in a concrete example. For this let
$\Sigma^*$ not be the set of all strings, but only the set of strings
upto a length of 3 over the alphabet $\{a, b\}$. That means $\Sigma^*$
(or the rectangle in the picture above) consists of the strings

\[
  \Sigma^* = \left\{\begin{array}{l}
    $\ensuremath{[]}$\\
    $\ensuremath{[a], [b]}$\\
    $\ensuremath{[aa], [ab], [ba], [bb]}$\\
    $\ensuremath{[aaa], [aab], [aba], [abb], [baa], [bab], [bba], [bbb]}$
    \end{array}\right\}
\] 


\noindent
If we set $A$ to $\{[aaa], [abb], [aa], [bb], []\}$, then $Der\;a\;A$ is the subset

\[
Der\;a\;A = \{[aa], [bb], [a]\}
\]  

\noindent
which is given by the definition of
$Der\;a\;A \dn \{s \in \Sigma^*\;|\;a::s\in A\}$. Now lets look at what
the complement of this set looks like:

\begin{equation}\label{Der}
  \overline{Der\;a\;A} = \left\{\begin{array}{l}
    $\ensuremath{[]}$\\
    $\ensuremath{[b]}$\\
    $\ensuremath{[ab], [ba]}$\\
    $\ensuremath{[aaa], [aab], [aba], [abb], [baa], [bab], [bba], [bbb]}$
    \end{array}\right\}
\end{equation}

\noindent
This can be calculated by ``subtracting'' $\{[aa], [bb], [a]\}$ from
$\Sigma^*$. I let you check whether I did this correctly.  According
to the equation in \eqref{eq} this should be equal to

\[
\overline{Der\;a\;A} = \{s \in \Sigma^*\;|\;a::s\not\in A\}
\]  

\noindent Let us test in turn every string in $\Sigma^*$ and see
whether $a::s$ is in $A$ which we set above to

\[\{[aaa], [abb], [aa], [bb], []\}\]

\noindent
This gives rise to the following table where in the first column are
the strings of $\Sigma^*$ and in the second whether $a::s \in A$ holds. The third column
is the negated version of the second.

\begin{center}
\begin{tabular}{r|c|l}
  s & is $a::s \in A$? & $\neg(a::s \in A) \Leftrightarrow  a::s \not\in A$\\
  \hline
  $[]$    & no & yes\\
  $[a]$   & yes& no\\
  $[b]$   & no & yes\\
  $[aa]$  & yes& no\\
  $[ab]$  & no & yes\\
  $[ba]$  & no & yes\\
  $[bb]$  & yes& no\\
  $[aaa]$ & no & yes\\
  $[aab]$ & no & yes\\
  $[aba]$ & no & yes\\
  $[abb]$ & no & yes\\
  $[baa]$ & no & yes\\
  $[bab]$ & no & yes\\
  $[bba]$ & no & yes\\
  $[bbb]$ & no & yes\\
\end{tabular}    
\end{center}

\noindent
Collecting all the yes in the third row gives you the set in \eqref{Der}. So it works out in this example.

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: