FSM

A deterministic finite state machine (a.k.a. finite automaton) simulator made in Java. Requires Java 1.5+.

In the summer of 2008, I took a class called "Intro. to CS Theory" where I learned about different types of state machines and their formal definitions. During this class, I was inspired to write a state machine simulator so that I could test some of my homework answers. The end result is a couple of classes and a meta-language for ease of use.

The classes

The classes are the machine itself (FSM.java), a nested State class, an Exception class, and the meta-language decoder (MakeFSM.java).They are available in this jar file. The main class is MakeFSM. It takes one file as an argument, where it will read your meta-language code, or no arguments, which will then cause it to read your meta-language code from standard input.

The meta-language

The meta-language only has a few commands and there is no error checking done by MakeFSM. The commands are:

  • states
  • accept
  • normal
  • trans
  • start
  • run
  • trace

The commands "states", "normal", and "accept" all take comma separated lists of state names as arguments. "States" creates states with the given names. "Normal" makes the given states normal (non-accepting) states. "Accept" makes the given states accepting states. "Trans" takes a state name, an input character, and another state. It creates a transition from the first state on the input character to the second state. "Start" takes one state name as an argument and makes it the starting state for the machine (overwrites any previous "start" commands). "Run" and "trace" both take an input string as an argument and tell you whether or not the machine accepts on that string (by printing "true" or "false"), but "trace" will also print all of the transitions made by the machine on the way there.

Consider the following state machine which accepts all strings which contain any number of 0's and at least two 1's:

Meta-language code for the above machine could look like this:

states q0, q1, q2
start q0
accept q2
normal q1, q0
trans q0, "1", q1
trans q1, "1", q2
trans q2, "1", q2
trans q2, "0", q2
trans q0, "0", q0
trans q1, "0", q1
trace "10010"
run "1000"
run "01011010"
run "12"

Its output looks like this:

q0, q1 on 1, q1 on 0, q1 on 0, q2 on 1, q2 on 0
10010: true
1000: false
01011010: true
No transition from q1 on 2
12: false

The message "No transition from q1 on 2" is on standard error. Numbers as input characters should be quoted. State names containing spaces or punctuation should also be quoted. By default, states are set as normal, but being explicit doesn't hurt.

Occasions for use

This FSM simulator will not work on nondeterministic state machines. It will not draw the machines for you (other programs are available for that). It will help you make sure your state machines act the way you expect. It is useful for computer science and some basic digital design.