
diff -r 4e628958c01a -r 6718ef6143b8 handouts/ho03.tex
--- a/handouts/ho03.tex	Sat Sep 26 23:45:40 2020 +0100
+++ b/handouts/ho03.tex	Sun Sep 27 09:15:32 2020 +0100
@@ -1560,40 +1560,68 @@
 
 \subsection*{Where Have Derivatives Gone?}
 
-Still to be done\bigskip
+%%Still to be done\bigskip
+
+\noindent
+By now you are probably fed up with this text. It is now way too long
+for one lecture, but there is still one aspect of the
+automata-regular-expression-connection I like to describe:\medskip
 
-%\noindent
-%By now you are probably fed up with this text. It is now way too long
-%for one lecture, but there is still one aspect of the
-%automata-regular-expression-connection I like to describe. Perhaps by
-%now you are asking yourself: Where have the derivatives gone? Did we
-%just forget them?  Well, they have a place in the picture of
-%calculating a DFA from the regular expression.
+\noindent
+Where have the derivatives gone? Did we just forget them?  Well, they
+actually do play a role of generating a DFA from a regular expression.
+And we can also see this in our implementation\ldots{}because there is
+one flaw in our representation of automata and transitions as partial
+functions. We can represent automata with infinite states, which is
+actually forbidden by the definition of what an automaton is. We can
+exploit this flaw as follows: Suppose our alphabet consists of the
+characters $c_1$ to $c_n$. Then we can generate an ``automaton''
+(it is not really one because it has infinite states) by taking
+as starting state the regular expression $r$ for which we
+want to generate an automaton. There are $n$ next-states which
+corresponds to the derivatives of $r$ according to $c_1$ to $c_n$.
+Implementing this in our slightly ``flawed'' representation is
+not too difficult. This will give a picture for the ``automaton''
+looking something like this, except that it extends infinitely
+far to the right:
+
 
-%To be done
-%
-%\begin{center}
-%\begin{tikzpicture}
-%  [level distance=25mm,very thick,auto,
-%   level 1/.style={sibling distance=30mm},
-%   level 2/.style={sibling distance=15mm},
-%   every node/.style={minimum size=30pt,
-%                    inner sep=0pt,circle,draw=blue!50,very thick,
-%                    fill=blue!20}]
-%  \node {$r$} [grow=right]
-%  child[->] {node (cn) {$d_{c_n}$}
-%    child { node {$dd_{c_nc_n}$}}
-%    child { node {$dd_{c_nc_1}$}}
-%    %edge from parent node[left] {$c_n$}
-%  }
-%  child[->] {node (c1) {$d_{c_1}$}
-%    child { node {$dd_{c_1c_n}$}}
-%    child { node {$dd_{c_1c_1}$}}
-%    %edge from parent node[left] {$c_1$}
-%  };
-%  %%\draw (cn) -- (c1) node {\vdots}; 
-%\end{tikzpicture}  
-%\end{center}
+\begin{center}
+\begin{tikzpicture}
+ [level distance=25mm,very thick,auto,
+  level 1/.style={sibling distance=30mm},
+  level 2/.style={sibling distance=15mm},
+  every node/.style={minimum size=30pt,
+                   inner sep=0pt,circle,draw=blue!50,very thick,
+                   fill=blue!20}]
+ \node {$r$} [grow=right]
+ child[->] {node (cn) {$d_{c_n}$}
+   child { node {$dd_{c_nc_n}$}}
+   child { node {$dd_{c_nc_1}$}}
+   %edge from parent node[left] {$c_n$}
+ }
+ child[->] {node (c1) {$d_{c_1}$}
+   child { node {$dd_{c_1c_n}$}}
+   child { node {$dd_{c_1c_1}$}}
+   %edge from parent node[left] {$c_1$}
+ };
+ %%\draw (cn) -- (c1) node {\vdots}; 
+\end{tikzpicture}  
+\end{center}
+
+\noindent
+I let you implement this ``automaton''.
+
+While this makes all sense (modulo the flaw with the infinite states),
+does this automaton teach us anything? The answer is no, because it
+boils down to just another implementation of the Brzozowski
+algorithm. There \emph{is} something interesting in this construction
+which Brzozowski already cleverly found out, because there is
+a way to restrict the number of states to something finite.
+However, this would lead us far, far away from what we should
+discuss here.
+
+
 
 %\section*{Further Reading}
 
@@ -1601,7 +1629,6 @@
 %regular expression $a\cdot (b + c)^*$ and what the Thomson
 %algorithm generates.
 
-%http://www.inf.ed.ac.uk/teaching/courses/ct/
 \end{document}
 
 %%% Local Variables: 




