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 |