1563 Still to be done\bigskip

  1563 %%Still to be done\bigskip

  1564 

  1564 

  1565 %\noindent

  1565 \noindent

  1566 %By now you are probably fed up with this text. It is now way too long

  1566 By now you are probably fed up with this text. It is now way too long

  1567 %for one lecture, but there is still one aspect of the

  1567 for one lecture, but there is still one aspect of the

  1568 %automata-regular-expression-connection I like to describe. Perhaps by

  1568 automata-regular-expression-connection I like to describe:\medskip

  1569 %now you are asking yourself: Where have the derivatives gone? Did we

  1569 

  1570 %just forget them?  Well, they have a place in the picture of

  1570 \noindent

  1571 %calculating a DFA from the regular expression.

  1571 Where have the derivatives gone? Did we just forget them?  Well, they

  1572 

  1572 actually do play a role of generating a DFA from a regular expression.

  1573 %To be done

  1573 And we can also see this in our implementation\ldots{}because there is

  1574 %

  1574 one flaw in our representation of automata and transitions as partial

  1575 %\begin{center}

  1575 functions. We can represent automata with infinite states, which is

  1576 %\begin{tikzpicture}

  1576 actually forbidden by the definition of what an automaton is. We can

  1577 %  [level distance=25mm,very thick,auto,

  1577 exploit this flaw as follows: Suppose our alphabet consists of the

  1578 %   level 1/.style={sibling distance=30mm},

  1578 characters $c_1$ to $c_n$. Then we can generate an ``automaton''

  1579 %   level 2/.style={sibling distance=15mm},

  1579 (it is not really one because it has infinite states) by taking

  1580 %   every node/.style={minimum size=30pt,

  1580 as starting state the regular expression $r$ for which we

  1581 %                    inner sep=0pt,circle,draw=blue!50,very thick,

  1581 want to generate an automaton. There are $n$ next-states which

  1582 %                    fill=blue!20}]

  1582 corresponds to the derivatives of $r$ according to $c_1$ to $c_n$.

  1583 %  \node {$r$} [grow=right]

  1583 Implementing this in our slightly ``flawed'' representation is

  1584 %  child[->] {node (cn) {$d_{c_n}$}

  1584 not too difficult. This will give a picture for the ``automaton''

  1585 %    child { node {$dd_{c_nc_n}$}}

  1585 looking something like this, except that it extends infinitely

  1586 %    child { node {$dd_{c_nc_1}$}}

  1586 far to the right:

  1587 %    %edge from parent node[left] {$c_n$}

  1587 

  1588 %  }

  1588 

  1589 %  child[->] {node (c1) {$d_{c_1}$}

  1589 \begin{center}

  1590 %    child { node {$dd_{c_1c_n}$}}

  1590 \begin{tikzpicture}

  1591 %    child { node {$dd_{c_1c_1}$}}

  1591  [level distance=25mm,very thick,auto,

  1592 %    %edge from parent node[left] {$c_1$}

  1592   level 1/.style={sibling distance=30mm},

  1593 %  };

  1593   level 2/.style={sibling distance=15mm},

  1594 %  %%\draw (cn) -- (c1) node {\vdots}; 

  1594   every node/.style={minimum size=30pt,

  1595 %\end{tikzpicture}  

  1595                    inner sep=0pt,circle,draw=blue!50,very thick,

  1596 %\end{center}

  1596                    fill=blue!20}]

  1597  \node {$r$} [grow=right]

  1598  child[->] {node (cn) {$d_{c_n}$}

  1599    child { node {$dd_{c_nc_n}$}}

  1600    child { node {$dd_{c_nc_1}$}}

  1601    %edge from parent node[left] {$c_n$}

  1602  }

  1603  child[->] {node (c1) {$d_{c_1}$}

  1604    child { node {$dd_{c_1c_n}$}}

  1605    child { node {$dd_{c_1c_1}$}}

  1606    %edge from parent node[left] {$c_1$}

  1607  };

  1608  %%\draw (cn) -- (c1) node {\vdots}; 

  1609 \end{tikzpicture}  

  1610 \end{center}

  1611 

  1612 \noindent

  1613 I let you implement this ``automaton''.

  1614 

  1615 While this makes all sense (modulo the flaw with the infinite states),

  1616 does this automaton teach us anything? The answer is no, because it

  1617 boils down to just another implementation of the Brzozowski

  1618 algorithm. There \emph{is} something interesting in this construction

  1619 which Brzozowski already cleverly found out, because there is

  1620 a way to restrict the number of states to something finite.

  1621 However, this would lead us far, far away from what we should

  1622 discuss here.

  1623 

  1624