\documentclass{article}

\usepackage{../style}

\usepackage{../graphics}

\title{Derivative for the NOT-Regular Expression}

\begin{document}

\maketitle

\begin{abstract}

  \noindent

  This short note explains why the derivative for the NOT-regular

  expression is defined as

  \[

  der\,c(\sim r) \;\dn\; \sim (der\,c\,r)

  \]

  The explanation goes via complement sets, the semantic derivative (\textit{Der})

  and how the derivative relates to the semantic derivative.

\end{abstract}

\section*{Complement Sets}

To start with, 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 in this section

also holds for any kind of ``domain'', like the set of all integers or

the set of all binary trees, etc).\footnote{NOTE: In the videos and slides I use \textit{UNIV} as notation for $\Sigma^*$. } 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)

\medskip

\noindent

The conclusion is: if we want the property $L(der\,c\,r) = Der\,c\,(L(r))$ to hold and the

semantics of $\sim r$ is defined as $\overline{L(r)}$, then the definition for the derivative

for the NOT-regular expression must be:

\[

der\,c(\sim r) \;\dn\; \sim (der\,c\,r)

\]  

\end{document}

%%% Local Variables: 

%%% mode: latex

%%% TeX-master: t

%%% End: