FSAs
Home Up

 

 

Animating Finite State Automata

a component of

Animating the Theory of Computing

a primary thrust of the

Webworks Laboratory

 

Animating the Theory of Computing

Developing the tools necessary for animating the theory of computing is perhaps the most ambitious project of the Webworks Laboratory.  It is our goal to provide the tools necessary for a "hypertextbook" on the theory of computing that allows students to explore computing theory through interactive animations.  The eventual objective is to provide an environment in which students can learn even the deeper aspects of the theory, such as NP-completeness. 

The Craftsman

Webworks team member Michael Grinder is the lead person on this project.  His PhD thesis is on animating the theory of computing.  His first module is a finite state automaton animator, upon which he will be able to build all of the other necessary models of computation.  The FSA animator has been used very successfully in sophomore level courses, the freshman theory course, the senior compiler course, and the graduate theory course.  It has also been featured an a number of educational conferences, including SIGCSE.

Features

There are a number of features in the animator.

bullet
Instructions.  Directions on how to use the animator are available in the animatrion window.
bullet
A library of finite state automata ready for animation.  There are only a few examples in the library at present, but the number can be exteneded arbitrariy far by an instructor.
bullet
String submission.  The user can type in arbitrary strings for processing by the chosen finite state automaton.
bullet
Stepping control.  The user can cause execution of the fsa on an input string to proceed a step at a time by simple mouse clicks.
bullet
Continuous execution.  Stepping control can be turned off.
bullet
Editing.  A user can modify a finite state automaton, or indeed, build an entirely new one by selecting the edit button and following the directions on building and moving states, arrows, and labels.
bullet
Sound.  If you turn your volume up, you can hear our exploratory attempts at adding sound to animation.

While the finite state automaton animator is very flexible, this version does not allow a student to save examples constructed from with in the animator.  Saving from an applet was simply not allowed (for security reasons) until the most recent versions of the Java Virtual Machine.  The capability to save constructed finite state automata is just now being added as a new feature.

The FSA Animator

Click here to try it for yourself!  Remember to do the following:

bullet
Be PATIENT as the animator applet loads.    Once it is loaded, you can run the animations without delay. 
bullet
For best results, maximize your browser window so that you can see the entire animator.
bullet
Be sure to select the edit button  before you enter strings, select an FSA to animate, modify an fsa, or construct a new fsa.
bullet
Be sure to select the run button to run the fsa on an entered string.
bullet
And turn your sound up.