\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}\noindentwhere $\Sigma^*$ is in our case the set of all strings (what followsalso holds for any kind of ``domain'', like the set of all integers orthe set of all binary trees, etc). Let us assume $P(s)$ is a property thatis about strings, for example $P(s)$ could be ``the string $s$ hasan 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 greycircle. This subset of strings is often written as a comprehension like\begin{equation}\label{set}\{s \in \Sigma^*\;|\; P(s) \}\end{equation}\noindentmeaning 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 thatsometimes the property $P(s)$ holds for every string in$\Sigma^*$. Then the grey area would fill out the whole rectangle andthe set where $\neg P(s)$ holds is empty. Similarly, if the property $P(s)$holds for no string, then 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) \}}\]\noindentIt is the area of $\Sigma^*$ which isn't grey, that is $\Sigma^*$minus $\{s \in \Sigma^*\;|\; P(s) \}$, \textbf{or} written differentlyit is the set $\{s \in \Sigma^*\;|\; \neg P(s) \}$. That means it is theset of all the strings where $\neg P(s)$ holds. Consequently we havefor 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 definesa subset of strings (inside $\Sigma^*$). The correspondingproperty $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\}\]\noindentThat means $Der\;c\;A$ is some grey area inside $\Sigma^*$. Obviouslywhich subset, or which grey area, we are carving out from $\Sigma^*$ depends on what wechoose for $c$ and $A$.\bigskip\noindentLet 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 stringsupto 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\}\] \noindentIf we set $A$ to $\{[aaa], [abb], [aa], [bb], []\}$, then $Der\;a\;A$ is the subset\[Der\;a\;A = \{[aa], [bb], [a]\}\] \noindentwhich is given by the definition of$Der\;a\;A \dn \{s \in \Sigma^*\;|\;a::s\in A\}$. Now lets look at whatthe 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}\noindentThis can be calculated by ``subtracting'' $\{[aa], [bb], [a]\}$ from$\Sigma^*$. I let you check whether I did this correctly. Accordingto the equation in \eqref{eq} this should also be equal to\[\overline{Der\;a\;A} = \{s \in \Sigma^*\;|\;\neg(a::s\in A)\}\] \noindent Let us test in turn every string in $\Sigma^*$ and seewhether $a::s$ is in $A$ which we set above to\[\{[aaa], [abb], [aa], [bb], []\}\]\noindentThis gives rise to the following table where in the first column are allthe strings of $\Sigma^*$ and in the second whether $a::s \in A$ holds. The third columnis the negated version of the second, namely $\neg(a::s\in A)$ which is the same as$a::s\not\in A$.\begin{center}\begin{tabular}{r|c|l} $s\in\Sigma^*$ & 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}\noindentCollecting all the yes in the third column gives you the set in\eqref{Der}. So it works out in this example. The idea is that this always works out. ;o)\bigskip\noindentBTW, notice that all three properties are the same\[ \neg(a::s \in A) \quad\Leftrightarrow\quad a::s \not\in A \quad\Leftrightarrow\quad a::s \in \overline{A}\] \noindentThis means we have\begin{equation}\label{D}\overline{Der\;a\;A} = Der\;a\;\overline{A}\end{equation}\noindentI let you check whether this makes sense.\section*{Not-Regular Expression}With the equation in \eqref{D} we can also very quickly verify that the$der$-definition for the not-regular expression satisfies the propertyof derivatives, namely\begin{equation}\label{derprop}\forall c\,r.\;\;\;L(der\;c\;r) = Der\;c\;(L(r))\end{equation}\noindentholds. We defined the language of a not-regular expression as\[L(\sim r) \;\dn\; \Sigma^* - L(r)\] \noindentUsing the overline notation, maybe I should have defined this equivalently as\[L(\sim r) \;\dn\; \overline{L(r)}\] \noindentmeaning all the strings that $r$ \emph{cannot} match. We defined the derivative forthe not-regular expression as\[der\;c\;(\sim r) \;\dn\; \sim(der\;c\;r)\] \noindentThe big question is now does this definition satisfy the property in\eqref{derprop}? Lets see: We would have to prove this by induction on regularexpressions. When we are in the case for $\sim r$ the reasoning is as follows:\begin{center} \def\arraystretch{1.5}\begin{tabular}{llll} $L(der\;c\;(\sim r))$ & $\dn$ & $L(\sim (der\;c\;r))$ & by definition of $der$\\ & $\dn$ & $\overline{L(der\;c\;r)}$ & by definition of $L$\\ & $=$ & $\overline{Der\;c\;(L(r))}$ & by IH\\ & $=$ & $Der\;c\;\overline{(L(r))}$ & by \eqref{D}\\ & $\dn$ & $Der\;c\;(L(\sim r))$ & by definition of $L$\\\end{tabular} \end{center}\noindentThat means we have established the property of derivatives in the $\sim r$-case\dots{}yippee~;o)\end{document}%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: