summaryrefslogtreecommitdiff
path: root/Master/texmf-dist/doc/generic/pgf/text-en/pgfmanual-en-library-automata.tex
diff options
context:
space:
mode:
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.tex289
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: