--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/hws/Der.tex Fri Oct 13 23:49:34 2023 +0100
@@ -0,0 +1,168 @@
+\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: