handouts/ho03.tex
changeset 573 711bbc480998
parent 572 4a1739f256fd
child 578 6e5e3adc9eb1
equal deleted inserted replaced
572:4a1739f256fd 573:711bbc480998
  1534 
  1534 
  1535 \subsection*{Where Have Derivatives Gone?}
  1535 \subsection*{Where Have Derivatives Gone?}
  1536 
  1536 
  1537 Still to be done\bigskip
  1537 Still to be done\bigskip
  1538 
  1538 
  1539 \noindent
  1539 %\noindent
  1540 By now you are probably fed up with this text. It is now way too long
  1540 %By now you are probably fed up with this text. It is now way too long
  1541 for one lecture, but there is still one aspect of the
  1541 %for one lecture, but there is still one aspect of the
  1542 automata-regular-expression-connection I like to describe. Perhaps by
  1542 %automata-regular-expression-connection I like to describe. Perhaps by
  1543 now you are asking yourself: Where have the derivatives gone? Did we
  1543 %now you are asking yourself: Where have the derivatives gone? Did we
  1544 just forget them?  Well, they have a place in the picture of
  1544 %just forget them?  Well, they have a place in the picture of
  1545 calculating a DFA from the regular expression.
  1545 %calculating a DFA from the regular expression.
  1546 
  1546 
  1547 To be done
  1547 %To be done
  1548 
  1548 %
  1549 \begin{center}
  1549 %\begin{center}
  1550 \begin{tikzpicture}
  1550 %\begin{tikzpicture}
  1551   [level distance=25mm,very thick,auto,
  1551 %  [level distance=25mm,very thick,auto,
  1552    level 1/.style={sibling distance=30mm},
  1552 %   level 1/.style={sibling distance=30mm},
  1553    level 2/.style={sibling distance=15mm},
  1553 %   level 2/.style={sibling distance=15mm},
  1554    every node/.style={minimum size=30pt,
  1554 %   every node/.style={minimum size=30pt,
  1555                     inner sep=0pt,circle,draw=blue!50,very thick,
  1555 %                    inner sep=0pt,circle,draw=blue!50,very thick,
  1556                     fill=blue!20}]
  1556 %                    fill=blue!20}]
  1557   \node {$r$} [grow=right]
  1557 %  \node {$r$} [grow=right]
  1558   child[->] {node (cn) {$d_{c_n}$}
  1558 %  child[->] {node (cn) {$d_{c_n}$}
  1559     child { node {$dd_{c_nc_n}$}}
  1559 %    child { node {$dd_{c_nc_n}$}}
  1560     child { node {$dd_{c_nc_1}$}}
  1560 %    child { node {$dd_{c_nc_1}$}}
  1561     %edge from parent node[left] {$c_n$}
  1561 %    %edge from parent node[left] {$c_n$}
  1562   }
  1562 %  }
  1563   child[->] {node (c1) {$d_{c_1}$}
  1563 %  child[->] {node (c1) {$d_{c_1}$}
  1564     child { node {$dd_{c_1c_n}$}}
  1564 %    child { node {$dd_{c_1c_n}$}}
  1565     child { node {$dd_{c_1c_1}$}}
  1565 %    child { node {$dd_{c_1c_1}$}}
  1566     %edge from parent node[left] {$c_1$}
  1566 %    %edge from parent node[left] {$c_1$}
  1567   };
  1567 %  };
  1568   %%\draw (cn) -- (c1) node {\vdots}; 
  1568 %  %%\draw (cn) -- (c1) node {\vdots}; 
  1569 \end{tikzpicture}  
  1569 %\end{tikzpicture}  
  1570 \end{center}
  1570 %\end{center}
  1571 
  1571 
  1572 %\section*{Further Reading}
  1572 %\section*{Further Reading}
  1573 
  1573 
  1574 %Compare what a ``human expert'' would create as an automaton for the
  1574 %Compare what a ``human expert'' would create as an automaton for the
  1575 %regular expression $a\cdot (b + c)^*$ and what the Thomson
  1575 %regular expression $a\cdot (b + c)^*$ and what the Thomson