
diff -r 38456acd29f3 -r 7f52427568ff hws/Der.tex
--- a/hws/Der.tex	Fri Oct 13 23:49:34 2023 +0100
+++ b/hws/Der.tex	Sat Oct 21 09:09:09 2023 +0100
@@ -25,7 +25,7 @@
 \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
+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
@@ -42,8 +42,8 @@
 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.
+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
@@ -55,7 +55,7 @@
 \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
+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:
 
@@ -63,7 +63,7 @@
 \overline{\{s \in \Sigma^*\;|\; P(s) \}} = \{s \in \Sigma^*\;|\; \neg P(s) \}
 \end{equation}
 
-\section*{Semantic derivative}
+\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
@@ -75,7 +75,7 @@
 
 \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
+which subset, or which grey area, we are carving out from $\Sigma^*$ depends on what we
 choose for $c$ and $A$.\bigskip
 
 
@@ -119,10 +119,10 @@
 \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
+to the equation in \eqref{eq} this should also be equal to
 
 \[
-\overline{Der\;a\;A} = \{s \in \Sigma^*\;|\;a::s\not\in A\}
+\overline{Der\;a\;A} = \{s \in \Sigma^*\;|\;\neg(a::s\in A)\}
 \]  
 
 \noindent Let us test in turn every string in $\Sigma^*$ and see
@@ -131,13 +131,14 @@
 \[\{[aaa], [abb], [aa], [bb], []\}\]
 
 \noindent
-This gives rise to the following table where in the first column are
+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.
+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 & is $a::s \in A$? & $\neg(a::s \in A) \Leftrightarrow  a::s \not\in A$\\
+  $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\\
@@ -158,7 +159,78 @@
 \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.
+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}
 




