Drawing Finite Automata and State Machines

I had to draw couple of Finite Automata and Turing Machines for some university assignments. Usually I would have done it using Inkscape (as it is my favorite tool for creating figures for my LaTeX documents), but doing it manually is pretty tedious work. Inkscape diagram tool is currently sub par, so everything have to be done by hand. It’s OK if you need to draw one State Machine once in a while, but not suitable for larger quantities. I’ve also tried using Dia, but it also required lots of manual tweaking and tuning.

To my surprise, Graphviz (and especially the dot utility) turned out to be the (almost) perfect tool for the job. It lets you describe the graph in a simple text-based way, and it handles the graph layout by himself. This is somewhat like LaTeX but for graphs (you concentrate on content not layout).

My Finite Automata needed no manual tweaking and resulted in a very nice graphs. For more complicated State Machines it’s sometimes necessary to do some manual tuning. The commands I found most useful to tweak the graph were:

  • Grouping nodes to be in the same level – { rank="same"; "q1"; "q2"; "q3"}. The other options for rank can affect how the group is positioned relative to the other nodes in the graph (source, above all, sink bellow all).
  • Adding weight to edges – q1 -> q2 [weight="10"]. This affects the cost of strecting the edge. The higher the weight the straighter the edges will be.
  • Adding invisible edges – q1 -> q3 [style="invis"]. This allowed me to control the order of the nodes in the same rank (height).

Last but not least Graphivz can generate the graphs in variety for formats including eps, pdf and svg (which allows post-processing with inkscape).

5 thoughts on “Drawing Finite Automata and State Machines

  1. Gadi Aleksandrowicz

    I’ve found graphviz less than satisfying for this job. The main problem is that graphviz can’t handle LaTeX, so things that are standard in drawing automatas are hard (or impossible) to create – for example, \varepsilon and q_0 won’t show up as they’re supposed to.

    There’s a nice utility called ladot which enables usage of LaTeX with dot, however it seems to generate LaTeX documents, which is not good if all I want is a picture (to embed in a non-LaTeX document). What can be done regarding these problems?

  2. Guy Post author

    Hi Gadi,

    As I’ve mentioned in the post, exporting the automata to svg allows post-processing with Inkscape (actually you can also do it for the eps and pdf output). Inkscape, allows you to add real LaTeX formulas and save the result as eps/pdf which is perfect for LaTeX, or in rasterized formats. (png etc.)

    Inkscape: http://www.inkscape.org/

    BTW nice blog you have there. I find good math resources aimed at people without academic background in the subject to be important tool in bringing people closer to mathematics.

  3. Gadi Aleksandrowicz

    The saga continued – I tried using Inkscape for LaTeX, but the default LaTeX feature (in the “effects”) menu seemed to disappear, and only appeared after I’ve installed the textext plugin.

    Afterwards, it still didn’t work – seems like this is a well-known (and yet unsolved – patch offered in the link didn’t work) problem:

    https://bugs.launchpad.net/ubuntu/+source/inkscape/+bug/55273

    textext itself does not appear anywhere on the effects menu.

    All in all, not a good Linux experience. This is something we better not tell the Windows people about.

Leave a Reply

Your email address will not be published. Required fields are marked *

 

This site uses Akismet to reduce spam. Learn how your comment data is processed.