PDA

A deterministic pushdown 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. That was this project. I have since adapted it to be a pushdown automaton simulator. Here is an explanation of the new simulator.

The classes

The classes are the machine itself (PDA.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 MakePDA. 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 start state name, an end state name, an input character, a top-of-stack (TOS) character ("Z" for the initial stack character), and a String to push back onto the stack (from top to bottom). It creates a transition from the first state on the input character and TOS character to the second state, which will push the given String on to the stack when taken. "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.

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.
Comments