Download your copy of STAX, the finite state machine compiler and simulator stax-0.5.3.tar.gz, by, John Haskins, Jr. today!

STAX is a programming language designed to develop various types of finite state machines which utilize zero, one or multiple stacks: Deterministic Finite Automata (DFAs), Non-deterministic Finite Automta (NFAs) and Push-down Automata (PDAs). DFAs and NFAa are finite state machines which do not utilize any stacks at all; PDAs utilize one or more stacks. [NOTE: A PDA with two or more stacks has computational power equivalent to a Turing machine, (i.e., can recognize any decidable language).]

STAX was inspired by my theory of computation professor who made it---the semester project, that is---30% of the total grade in the class. [NOTE (to my CS660 classmates): Heeeeeeeeeeeeeeeeeey! I didn't want to suffer from the Deep Impact phenomenon.]

What is stax-0.5.3.tar.gz and how do I use it?

stax-0.5.3.tar.gz is a tar-ed, gzip-ed archive, containing the source files for building the STAX compiler/simulator executables (stax & staxinterpreter) and several sample programs. The source files should easily compile and run on many different flavors of UNIX and UNIX-like systems (e.g., Linux, FreeBSD, NetBSD, OpenBSD, BSDI, NeXT, BeOS, IRIX, OSF/1, Mach, Solaris, SunOS, AIX, HP/UX). The compilation proceduer described in the Makefile has been tested with GNU's versions of the C compiler, yacc and lex; gcc v2.95.2, bison v1.28 and flex v2.5.4, respectively.

To unpack the archive, gunzip and un-tar as in the example below:

gunzip -c stax-0.5.3.tar.gz | tar -xvf -

All files should be deployed into a directory named stax-0.5.3. To build the executables,

cd stax-0.5.3
make

If you are able to run as root, you may fully install STAX by copying the stax and staxinterpreter executables to the /usr/bin or /usr/local/bin directory.

Voila! STAX is ready to go; to compile and execute a STAX program enter stax source-filename input-string at the command line. For example, to run the seventh sample program, enter:

stax p7.stax 0000$

at the command-line. (Make sure that your paths are properly set so that the system will be able to find the executables.) stax will compile the source file (p7.stax) into object code that can be run by the STAX simulator. If the source program successfully compiles, the simulator will start automatically, using the input string ``0000$'' as input to the resulting finite state machine. Note the trailing dollar sign appened to the input string; this is essential. The '$' character is reserved in the STAX programming language. It is used to mark the end-of-input and the bottom-of-stack.

As the simulator executes, it will print (presently, somewhat cryptic) messages describing the status of the machine's execution. When the simulator finishes, it will print:

main(): executor("0000$")=1

The main() function of STAX system is responsible for calling the executor() function whose parameter is the input string ``0000$''. executor() returns 0 if the finite state machine described by the source program (p7.stax, here) does not accept the input string; 1 if it does. When executor() returns 6, an erroneous input occured (i.e., the input string contains characters not defined in the machine's input alphabet); 8 denotes an underflow in one of the stacks (i.e., performing a pop operation on an empty stack).

A complete explaination of STAX is provided in the README.stax-0.5.3 file supplied with the archive.

Tell me about the sample programs.

The sample programs showcase the capabilities of STAX. For your convenience, links to the source-code for each are listed below (with the class of the language they accept in parenthesis):

Please refer to the README.stax-0.5.3 file.

What are the known glitches in STAX?

Although STAX allows users to compile and simulate non-deterministic machines, it is not truely, purely non-deterministic, of course. A truely non-deterministic machine (theoretically defined) can spawn as many copies of itself as necessary until it reaches an accepting state. The STAX simulator can only create 1024 copies, maximum. For those who have tons of RAM in their systems, the maximum number of copies may be increased by changing the line:

#define	NPDA		1024

in the stax.h file and recompiling.

What is new in STAX 0.5.*?

After a long vacation away from STAX, I have just completed a series of source code cleanup projects. It may still be a bit hard to follow, but I intend to clean it up even more. The previous version, STAX 0.15 contained numerous dead ends in the code: error conditions that were improperly handled or not addressed at all. I have made an ernest effort to identify and correct these omissions. Thus, the newer version should notify users with intelligible error messages instead of dumping core.

Also new, are self-expanding stacks! STAX 0.15 statically allocated 256 bytes of stack space per stack within each PDA data structure. This depth was not only arbitrary, but limiting, causing the old version to halt and report a stack overflow if more than 256 characters were pushed onto any of a PDA's stacks. This setup was also wasteful in the event that many fewer than 256 bytes per stack were necessary. The revised stack allocation code now dynamically allocates stack space in 32-byte chunks upon demand (i.e., in response to a push to a full stack). This drastically improved STAX' flexibility and efficiency.

The jump from version 0.5.0 to 0.5.3 is the result of numerous fixes to the main STAX simulator core. I am very pleased to offer the most bug-free version of STAX ever, plus two new sample STAX programs!

What are the author's plans for the future of STAX?

More than anything, I would someday like to develop a more user-friendly front end which graphically displays the results of the simulator. This more user-friendly interface would search for regular expressions in the simulator's output, digest them and feed the result to a Tcl/Tk script which would be responsible for graphically displaying the output of the machines as they execute. With this new tool, animations of the simulation could be either stored,

stax p7.stax 0000$ > p7.animation

and replayed later,

staxanimator < p7.animation

or played immediately after successful compilation,

stax p7.stax 0000$ | staxanimator

So there was a method to my madness when I created the simulator to spit out tons and tons of cryptic information! Any one who is good with developing such scripts should feel free to create their own and exploit STAX' vast flexibility; please send a copy to me if you do.

An interesting footnote: STAX is perfectly suited to the task of finding and identifying regular expressions (as would be necessary to develop the user-friendly front end, aforementioned)... a tool like Perl or awk, however, would be much more practical to use.

I will also develop more examples of STAX programs to add to the collection that comes bundled with the source.

Finally, for the severly RAM-challenged, I may implement a fundamentally different simulator core. The current algorithm spawns new copies of the presently-executing PDA when necessary, to achieve the illusion of non-determinism. Another alternative would be to enumerate every execution path history one transition at a time, keeping track of those that prove fruitless (ending in an error or in a non-accepting state). Fruitless paths would pruned from the enumeration tree as the simulation executes. While this technique would likely require a great deal longer to execute, the demand for RAM (to hold the multiple PDAs and all their stacks) would be reduced significantly. In fact, a step-by-step enumeration of path histories would be much simpler to draw on-screen because I would only have to worry about a single PDA rather than the potentially hundreds of simultaneously active PDAs (among which I cannot select the successful PDA until its conclusion) spawned by the current approach. Opinions? Feedback?

How do I contact the author?

I can be contacted via e-mail at predator@cs.virginia.edu. Please note that I am a full-time student. Therefore, I will not be able to provide proper support for STAX, the sample programs or any other part of the distribution. I will attempt to respond to all e-mails, bug reports, et cetera in a timely fashion, but offer no promises.

I would be very interested in feedback from teachers of computation theory who are brave enough to utilize this (admittedly crude) version of STAX in their course(s). What is STAX' value as a pedagogical tool?

Notes and final comments...

STAX is intended to augment theoretical computer scientists' toolset. Constructing a program to describe the functionality of a finite state machine is more precise than a prose description. Furthermore, having a compiler and simulator to run the program aids debugging the machine.

Legalese...

Neither I, the author nor the University of Virginia guarantee the suitability of STAX for any purpose, that the executables or any other part of the distribution be stable, correct or bug-free. STAX is free software, offered in the hope that others will find it useful and elucidating. Use at your own risk.

Latest version: 29 August 2006

STAX, Finite State Machine Compiler & Simulator. Copyright (C) 1998,1999,2001 John Haskins, Jr.