\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+ −
the 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, 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) \}}+ −
\]+ −
+ −
\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 is 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 which 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 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 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 all+ −
the strings of $\Sigma^*$ and in the second whether $a::s \in A$ holds. The third column+ −
is 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}+ −
+ −
\noindent+ −
Collecting 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+ −
+ −
\noindent+ −
BTW, 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}+ −
\] + −
+ −
\noindent+ −
This means we have+ −
+ −
\begin{equation}\label{D}+ −
\overline{Der\;a\;A} = Der\;a\;\overline{A}+ −
\end{equation}+ −
+ −
\noindent+ −
I 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 property+ −
of derivatives, namely+ −
+ −
\begin{equation}\label{derprop}+ −
\forall c\,r.\;\;\;L(der\;c\;r) = Der\;c\;(L(r))+ −
\end{equation}+ −
+ −
\noindent+ −
holds. We defined the language of a not-regular expression as+ −
+ −
\[+ −
L(\sim r) \;\dn\; \Sigma^* - L(r)+ −
\] + −
+ −
\noindent+ −
Using the overline notation, maybe I should have defined this equivalently as+ −
+ −
\[+ −
L(\sim r) \;\dn\; \overline{L(r)}+ −
\] + −
+ −
\noindent+ −
meaning all the strings that $r$ \emph{cannot} match. We defined the derivative for+ −
the not-regular expression as+ −
+ −
\[+ −
der\;c\;(\sim r) \;\dn\; \sim(der\;c\;r)+ −
\] + −
+ −
\noindent+ −
The big question is now does this definition satisfy the property in+ −
\eqref{derprop}? Lets see: We would have to prove this by induction on regular+ −
expressions. 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}+ −
+ −
\noindent+ −
That 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: + −