# Finite State Automata

A PostScript macro package to draw diagrams of Finite State Automata

## Drawing an automaton

The file with sample code contains all PostScript definitions needed to draw a finite state automaton. Just make a copy and modify to your needs as described below. The result can be used as Encapsulated PostScript.

The start of the file contains some settings to be adjusted to personal taste:

/NodeR  20 def                  % Radius for node circle
/ENodeR NodeR 0.8 mul def       % Radius for inner circle of final node
/LoopR  NodeR 4   mul def       % Radius for loop arc
/LoopW  30 def                  % Width for loop arc (degrees)
/NodeW   2 def                  % Linewidth for node circle
/ENodeW  1 def                  % Linewidth for inner circle of final node
/LineW   1 def                  % Linewidth for arcs

/Color true def                 % Should we use fill colors?


Defining an automaton

After a lot of subroutine definitions, the actual automaton is defined in the last section of the file:

    %%%%%%%% END OF HEADER %%%%%%%%

petersFSA begin

Automaton definition here
    end

showpage

%%EOF

Make sure you don't remove the lines shown above.

The first thing to do is to state what nodes to use, and where to put them in PostScript coordinate space. This example defines two nodes:

    /q0 [ 100 600 ] def
/q1 [ 180 700 ] def

Next, the nodes must be drawn. The command node takes four arguments: a node as defined above, and a red, a green, and a blue color value. These color values are used to fill in the node. The next example draws node q0 with a yellow fill color, and nodes q1 through q4 with a cyan fill color:
    q0 1 1 0 node
[ q1 q2 q3 q4 ] { 0 1 1 node } forall

If you disable fill colors (see Setting parameters) you still have to provide the color values.

Next, mark a node as initial node:

    q0 180 initialnode

The value 180 indicates that the mark should be at 180 degrees, meaning left.

Next, mark one or more nodes as final node:

    [ q2 q4 ] { finalnode } forall

Next, put labels inside the nodes:
    q0 amoveto [ (q) Rm (0) Sub ] Centre puttext
q1 amoveto [ (q) Rm (1) Sub ] Centre puttext

Here is a description of what the code between angle brackets does:

First a piece of text is defined, as in (q). In PostScript, all strings are put between round brackets.
Following is the keyword Rm. This means to put the preceding text in regular Roman typeface.
Another piece of text is defined, followed by the keyword Sub. This indicates the text should be typeset as a subscript.
A keyword Super can be used to typeset a text as a superscript. Other keywords are Sym (use symbol font), and Ovl (overline text).
A weird choice of options, overlined text, but no underlined text? Well... this is what I actually needed when I wrote this ;-)
Following the closing angle bracket is the keyword Centre. This means the text between angle brackets as a whole should be centered.

Texts can use all symbols from the ISO Latin 1 character set. To print an accented character, use a backslash followed by its three digit octal code. Example: \306 will print a Æ'.

Next, draw the arcs between the nodes. Some examples:

    q0 q1 20 .25 trans

This will draw an arc from node q0 to node q1, at an angle of 20 degrees from the imaginary straight line connecting the two nodes. The angle should be between -120 and 120 degrees.
The meaning of the fourth argument, the value .25 will be explained later.

Another example:

    q2 q2 90 .5 trans

Because start and end node are identical, this will draw a loop arc from the node onto itself. In this case, the third argument has a different meaning. It defines at what position the arc should be drawn. A value of 90 degrees will result in the arc being drawn at the top of the node.

Two more examples:

    q0 q2   0 .5 true  true  transition
q4 q4 270 .5 false false transition

Previous arcs always ended with an arrowhead at the second node. These two examples, using the transition command instead of the trans command uses two extra parameters: two booleans. The first states whether or not to draw an arrowhead at the start node, the second for the end node.

Finally, labels can be put near the arcs.

The fourth argument to the trans and transition commands defines a position. It should be a value between 0 and 1. When an arc is drawn, the currentpoint is set somewhere along the arc. A value of 0 will put it at the starting point, a value 1 at the end point, a value of .5 (the most useful) at the middle.

Each trans or transition command will shift the currentpoint to a new location. So, putting a label near the arc should be done immediately after an arc is draw:

    q0 q1  20 .5  trans    [ (A) Rm ] NorthWest puttext
q1 q0  20 .5  trans    [ (B) Rm ] SouthEast puttext

Here, the puttext command is used again. (It was first used to put labels inside nodes.) The keyword following the closing angle bracket states where, relative to currentpoint the text should be put. Valid keywords are Centre (used when putting labels inside nodes), North, East, South, West, NorthEast, NorthWest, SouthEast and SouthWest.

When all is done, the code should be tested, for example using the GV program, Ghostview, or GSView. Node positions may not be optimal, angle of arcs, positions of labels relative to arcs, etc.

Important: Don't forget to adjust the BoundingBox values at the second line of the file. These should be in order: X of left margin, Y of bottom margin, X of right margin, Y of top margin. Correct values are essential of you intend to import the figure into another document, such as a LaTeX file, using the \psfig command. Use GV, Ghostview, or GSView to determine the correct values.

## Using multiple figures

The PostScript code consists of a lot of subroutine definitions and a few lines to draw an actual automaton. When you're using dozens of these figures in a single document this results in a lot of unnecessary code duplication. To avoid this, the code can be split into a single header file, and one short file for each figure.

Once a figure is defined and tested, you can cut out all lines of code between these lines:

    %%%%%%%% START OF HEADER %%%%%%%%

. . . .
    %%%%%%%% END OF HEADER %%%%%%%%

Save these lines in a separate header file, e.g. named FSAheader.pro. When compiling your document, include this header file only once. Here's an example for LaTeX:
    \documentclass{article}
\usepackage{psfig}

    \begin{document}

    \psfig{figure=fsa1.ps}

    \psfig{figure=fsa2.ps}

    \end{document}
`