diff options
Diffstat (limited to 'Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-library-automata.tex')
-rw-r--r-- | Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-library-automata.tex | 289 |
1 files changed, 289 insertions, 0 deletions
diff --git a/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-library-automata.tex b/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-library-automata.tex new file mode 100644 index 00000000000..4f587a8bbab --- /dev/null +++ b/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-library-automata.tex @@ -0,0 +1,289 @@ +% Copyright 2006 by Till Tantau +% +% This file may be distributed and/or modified +% +% 1. under the LaTeX Project Public License and/or +% 2. under the GNU Free Documentation License. +% +% See the file doc/generic/pgf/licenses/LICENSE for more details. + + +\section{Automata Drawing Library} + +\begin{tikzlibrary}{automata} + This packages provides shapes and styles for drawing finite state + automata and Turing machines. +\end{tikzlibrary} + + +\subsection{Drawing Automata} + +The automata drawing library is intended to make it easy to draw +finite automata and Turing machines. It does not cover every +situation imaginable, but most finite automata and Turing machines +found in text books can be drawn in a nice and convenient fashion +using this library. + +To draw an automaton, proceed as follows: +\begin{enumerate} +\item For each state of the automaton, there should be one node with + the option |state|. +\item To place the states, you can either use absolute positions or + relative positions, using options like |above of| or |right of|. +\item Give a unique name to each state node. +\item Accepting and initial states are indicated by adding the + options |accepting| and |initial|, respectively, to the state + nodes. +\item Once the states are fixed, the edges can be added. For this, the + |edge| operation is most useful. It is, however, also possible to + add edges after each node has been placed. +\item For loops, use the |edge [loop]| operation. +\end{enumerate} + +Let us now see how this works for a real example. Let us consider a +nondeterminsitic four state automaton that checks whether an contains +the sequence $0^*1$ or the sequence $1^*0$. +\begin{codeexample}[] +\begin{tikzpicture}[shorten >=1pt,node distance=2cm,auto] + \draw[help lines] (0,0) grid (3,2); + + \node[state,initial] (q_0) {$q_0$}; + \node[state] (q_1) [above right of=q_0] {$q_1$}; + \node[state] (q_2) [below right of=q_0] {$q_2$}; + \node[state,accepting](q_3) [below right of=q_1] {$q_3$}; + + \path[->] (q_0) edge node {0} (q_1) + edge node [swap] {1} (q_2) + (q_1) edge node {1} (q_3) + edge [loop above] node {0} () + (q_2) edge node [swap] {0} (q_3) + edge [loop below] node {1} (); +\end{tikzpicture} +\end{codeexample} + + +\subsection{States With and Without Output} + +The |state| style actually just ``selects'' a default underlying +style. Thus, you can define multiple new complicated state style and +then simply set the |state| style to your given style to get the +desired kind of styles. + +By default, the following state styles are defined: +\begin{itemize} + \itemstyle{state without output} + This node style causes nodes to be drawn circles. Also, this style + calls |every state|. + \itemstyle{state with output} + This node style causes nodes to be drawn as split circles, that is, + using the |circle split| shape. In the upper part of the shape you + have the name of the style, in the lower part the output is + placed. To specify the output, use the command |\nodepart{lower}| + inside the node. This style also calls |every state|. +\begin{codeexample}[] +\begin{tikzpicture} + \draw[help lines] (0,0) grid (3,2); + + \node[state without output] {$q_0$}; + + \node[state with output] at (2,0) {$q_1$ \nodepart{lower} $00$}; +\end{tikzpicture} +\end{codeexample} + + \itemstyle{state} + This style is set to |state without output| by default. You should + redefine it to something else, if you wish to use states of a + different nature. +\begin{codeexample}[] +\begin{tikzpicture} + \tikzstyle{state}=[state with output] + \node[state] {$q_0$ \nodepart{lower} $11$}; + \node[state] at (2,0) {$q_1$ \nodepart{lower} $00$}; +\end{tikzpicture} +\end{codeexample} + + \itemstyle{every state} + This style is used by |state with output| and also by + |state without output|. By default, it does nothing, but you can use + it to make your state look more fancy: +\begin{codeexample}[] +\begin{tikzpicture}[shorten >=1pt,node distance=2cm,>=stealth'] + \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20] + + \node[state,initial] (q_0) {$q_0$}; + \node[state] (q_1) [above right of=q_0] {$q_1$}; + \node[state] (q_2) [below right of=q_0] {$q_2$}; + + \path[->] (q_0) edge node [above left] {0} (q_1) + edge node [below left] {1} (q_2) + (q_1) edge [loop above] node {0} () + (q_2) edge [loop below] node {1} (); +\end{tikzpicture} +\end{codeexample} +\end{itemize} + + +\subsection{Initial and Accepting States} + +The styles |initial| and |accepting| are similar to the |state| style +as they also just select an ``underlying'' style, which installs the +actual settings for initial and accepting states. + +For initial states, there is only one predefined way of drawing them, +so the two-stage mechanism is not really necessary, but, perhaps, +I will find another way of drawing them in the literature some time. + +Let us start with the initial states. +\begin{itemize} + \itemstyle{initial} + This style simply selects |initial by arrow|. + \itemstyle{initial by arrow} + This style causes an arrow and, possibly, some text to be added to + the node. The arrow points from the text to the node. The node text + and the direction and the distance can be set using the following + options: + \begin{itemize} + \itemoption{initial text}|=|\meta{text} sets the text to be + used. Use an empty text to suppress all text. The default is + |start|. + \itemoption{initial where}|=|\meta{direction} set the place where + the text should be shown. Allowed values are |above|, |below|, + |left|, and |right|. + \itemoption{intial distance}|=|\meta{distance} is the length of the + arrow leading from the text to the state node. + \end{itemize} + \itemstyle{every initial by arrow} + This style is executed at the beginning of every path that contains + the arrow and the text. You can use it to, say, make the text red or + whatever. +\begin{codeexample}[] +\begin{tikzpicture} + \tikzstyle{every initial by arrow}=[text=red,->>] + \node[state,initial,initial distance=2cm] {$q_0$}; +\end{tikzpicture} +\end{codeexample} + \itemstyle{initial above} is a shorthand for + |initial by arrow,initial where=above| + \itemstyle{initial below} works similarly to the previous option. + \itemstyle{initial left} works similarly to the previous option. + \itemstyle{initial right} works similarly to the previous option. +\end{itemize} + +For the accepting states, the sitation is similar: There is also an +|accepting| style that selects the way accepting states are +rendered. However, there are now two options: First, +|accepting by arrow|, which works the same way as |initial by arrow|, +only with the direction of arrow reversed, and |accepting by double|, +where accepting states get a double line around them. + +\begin{itemize} + \itemstyle{accepting} + This style selects |accepting by double| by default. You can replace + this by the style |accepting by arrow| to get accepting states with + an arrow leaving them. + \itemstyle{accepting by double} + Specifies that the node should get a double line around it. + \itemstyle{accepting by arrow} + This style causes an arrow and, possibly, some text to be added to + the node. The arrow points to the text from the node. + \begin{itemize} + \itemoption{accepting text}|=|\meta{text} sets the text to be + used. Use an empty text to suppress all text. This is the default. + \itemoption{accepting where}|=|\meta{direction} set the place where + the text should be shown. Allowed values are |above|, |below|, + |left|, and |right|. + \itemoption{intial distance}|=|\meta{distance} is the length of the + arrow. + \end{itemize} +\begin{codeexample}[] +\begin{tikzpicture} + [shorten >=1pt,node distance=2cm,>=stealth',initial text=] + + \tikzstyle{every state}=[draw=blue!50,very thick,fill=blue!20] + \tikzstyle{accepting}=[accepting by arrow] + + \node[state,initial] (q_0) {$q_0$}; + \node[state] (q_1) [above right of=q_0] {$q_1$}; + \node[state] (q_2) [below right of=q_0] {$q_2$}; + \node[state,accepting](q_3) [below right of=q_1] {$q_3$}; + + \path[->] (q_0) edge node [above left] {0} (q_1) + edge node [below left] {1} (q_2) + (q_1) edge node [above right] {1} (q_3) + edge [loop above] node {0} () + (q_2) edge node [below right] {0} (q_3) + edge [loop below] node {1} (); +\end{tikzpicture} +\end{codeexample} + \itemstyle{every accepting by arrow} + This style is executed at the beginning of every path that contains + the arrow and the text. + \itemstyle{accepting above} is a shorthand for + |accepting by arrow,accepting where=above| + \itemstyle{accepting below} works similarly to the previous option. + \itemstyle{accepting left} works similarly to the previous option. + \itemstyle{accepting right} works similarly to the previous option. +\end{itemize} + + + +\subsection{Examples} + +In the following example, we once more typeset the automaton presented +in the previous sections. This time, we use the following rule for +accepting/initial state: Initial states are red, accepting states are +green, and normal states are orange. Then, we must find a path from a +red state to a green state. + +\begin{codeexample}[] +\begin{tikzpicture}[shorten >=1pt,node distance=2cm,>=stealth',thick] + \tikzstyle{every state}=[fill,draw=none,orange,text=white] + \tikzstyle{accepting}=[green!50!black,text=white] + \tikzstyle{initial}= [red,text=white] + + \node[state,initial] (q_0) {$q_0$}; + \node[state] (q_1) [above right of=q_0] {$q_1$}; + \node[state] (q_2) [below right of=q_0] {$q_2$}; + \node[state,accepting](q_3) [below right of=q_1] {$q_3$}; + + \path[->] (q_0) edge node [above left] {0} (q_1) + edge node [below left] {1} (q_2) + (q_1) edge node [above right] {1} (q_3) + edge [loop above] node {0} () + (q_2) edge node [below right] {0} (q_3) + edge [loop below] node {1} (); +\end{tikzpicture} +\end{codeexample} + +The next example is the current candidate for the five-state busiest +beaver: + +\begin{codeexample}[] +\begin{tikzpicture}[->,>=stealth',shorten >=1pt,% + auto,node distance=2cm,semithick, + inner sep=2pt,bend angle=45] + \node[initial,state] (A) {$q_a$}; + \node[state] (B) [above right of=A] {$q_b$}; + \node[state] (D) [below right of=A] {$q_d$}; + \node[state] (C) [below right of=B] {$q_c$}; + \node[state] (E) [below of=D] {$q_e$}; + + \tikzstyle{every node}=[font=\footnotesize] + + \path (A) edge node {0,1,L} (B) + edge node {1,1,R} (C) + (B) edge [loop above] node {1,1,L} (B) + edge node {0,1,L} (C) + (C) edge node {0,1,L} (D) + edge [bend left] node {1,0,R} (E) + (D) edge [loop below] node {1,1,R} (D) + edge node {0,1,R} (A) + (E) edge [bend left] node {1,0,R} (A); +\end{tikzpicture} +\end{codeexample} + + +%%% Local Variables: +%%% mode: latex +%%% TeX-master: "pgfmanual-pdftex-version" +%%% End: |