# HG changeset patch # User Christian Urban # Date 1697237374 -3600 # Node ID c82a45f48bfc916bb9781b2d1a08d445d8238c9c # Parent 66adcae6c7620d9b4bae362d8954f89b5230b693 added complement note diff -r 66adcae6c762 -r c82a45f48bfc hws/Der.pdf Binary file hws/Der.pdf has changed diff -r 66adcae6c762 -r c82a45f48bfc hws/Der.tex --- /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: