The Java Computability Toolkit v1.0

Overview

About: The Java Computability Toolkit (JCT) contains a pair of graphical environments for creating and simulating NFAs, DFAs, and high level Turing Machines. JCT is written in 100% Java and makes heavy use of the new JFC Swing components. It is designed to run as an application or applet on any platform supporting either:
...1. ...JDK 1.1.5 and Swing 1.0.2 (or higher)
...2.... JDK1.2beta4 (or higher)
...3.... Java Plugin (if run in Applet mode)
When JDK1.2 compliant browsers are released the plugin will not be required to run JCT as an applet.

JCT was written as part of a Master's thesis and is intended to establish a groundwork for portable software that will not only help teach concepts of computational models, but will provide an environment for exploration and simulation of these models not practically possible otherwise. The current software forms the foundation of a toolkit to be continually expanded upon, maintained, and made available to the public. It is built with collaboration and user-friendliness in mind and it is free!

Finite Automata Environment: The Finite Automata Environment allows a user to create and simulate multiple NFAs and DFAs in cascading internal windows.

The following unary operations are allowed on FAs:

Convert To DFA, Minimize, Complement, Kleene Star,

The following binary operations are allowed on FAs:

Intersection, Concatenation, Union.

The Finite Automata Environment also features:

Compute on a given input: Types in a string and send it to the NFA/DFA for computation. If the string is accepted a list is generated displaying the transitions used in the [or one of the] optimum [shortest] acceptance path.

Trace acceptance path. If a string is accepted as the result of a Compute the user can choose to graphically walk through each configuration of the optimum acceptance path taken.

A Graph Representation.can be generated of any DFA or NFA.

Transition Grouping. Transitions which have the same "from" and "to" states are grouped together to reduce screen clutter. Each transition is separated into its own boxe and can be removed or modified without affecting other members of the group.

Moveable Transitions. Each transition group can be automatically positioned by JCT or manually positioned by the user.

Printing. Grabs an image of the current Finite Automata and prints it along with Author info.

Undo. One level of undo.

Save and Load. Finite Automata can be saved and loaded locally.

Turing Machine Environment: The Turing Machine Environment allows a user to create and simulate multiple Turing Machines in cascading internal windows.

The Turing Machine Environment features:

Infinite Two-way I/O Tapes. Infinite two-way tapes allow any possible input and output.

Execute/Run. The ability to Run a Turing Machine where operations occur every 0.5 seconds. The head can be "followed" or we can let it go off by itself [following the head keeps our view of the tape centered on the head wherever it goes]

Trace an execution. Ability to trace through the execution and examine the results of each operation performed.

'Nested' Machines. A Turing Machine that has been saved may be used as a sub-machine in any other machine. This funcionality provides the user with the ability to 'nest' Turing Machines to any level desired.

Self-Contained Machines: Each sub-machine loaded is loaded from a file. However, as soon as it is loaded it is no longer affiliated with that file and is completely contained in the Turing Machine being built.

Up to 52 Variables. The contents of a tape square can be stored into a variable for later use. Up to 52 such variables can be active in a Turing Machine at any given time.

Global / Local Variables: Variables are defined as either global or local. Global variables allow information to pass through to submachines. Local veraibles are specific to each sub-machine.

High Level Notation. This environment uses high level TM notation with L (move left), R (move right), Lx (move left until symbol 'x'), Rx (move right until symbol 'x') and x (write the symbol 'x'). L, R, Lx, Rx, and x are the basic building blocks you start out with in this environment. Sub-Machines can be inserted into any machine making it simple to build up a toolbox of useful machines.

Transition Grouping. Transitions which have the same 'from' and 'to' states are grouped together to reduce screen clutter. Each transition resides in a separate box and can be removed or modified without affecting other members of the group.

Moveable Transitions. Each transition group can be automatically positioned by JCT or manually positioned by the user.

State Grouping. Each state (sub-machine) of a Turing Machine is considered to be a member of a state group. States are grouped together by insertion. These groups can easily be split and in many cases JCT makes 'split decisions' that attempt to reduce screen clutter.

Printing. Grabs an image of the current Turing Machine and prints it along with Author info.

Undo. One level of undo.

Save and Load. Turing Machines can be saved and loaded locally. Saved Turing Machines can be used as sub-machines.

Save and Load Tape. The contents of the Input tape can be saved and loaded locally.

Who Is Responsible?

Dr. Jorge E. Novillo, jorge@sunyit.edu

Dr. Jorge Novillo is Associate Professor of computer science at SUNY Institute of Technology of Utica/Rome. Dr. Novillo teaches a course in Theory of Computation every year and plans to integrate JCT into this class.

Jason A. Hamshar, jason_hamshar@sterling.itd.com

Jason Hamshar is a Research Scientist in the Information Technology Division of Sterling Software in Rome, N.Y. He is also an M.S. student at SUNY Institute of Technology and has a B.S. in computer science from there as well. He has over 10 years professional experience programming in C and C++, and has worked with Java since its inception. Jason is the author of the JAT library which underlies JCT and contains most of the operational algorithms. This library is the subject of Jason's Masters project and several independent studies.

Matthew B. Robinson, matt@cs.clemson.edu, http://cyclone.cs.clemson.edu/~matt

Matt Robinson is an M.S. student and graduate assistant at SUNY Institute of Technology. He has a B.S. in mathematics from Bates College and is on his way to Clemson University for Ph.D. studies in computer science. Matt is the author of JCT and its construction is the subject of his Master's thesis. He is presently co-authoring a Swing book, has contributed work to a forthcoming Java3D book and has published techniques relevant to the creation of JCT in Sun's on-line Swing journal.

Other Similar Software:

Dr. Susan Rodger and the JFLAP team of Duke University were the first, as far as we know, to demonstrate robust Automata environments with Java. JFLAP is available for free download.
http://www.cs.duke.edu/~rodger/tools/jflap/

Dr.John Etchemendy of Stanford University and Dr. Jon Barwise of Indiana University in Bloomington have constructed Turing's World. This software uses lower level notation and allows nondeterministic Turing Machines resulting in, potentially, multiple output tape configurations. Turing's World also allows the user to "look into" the computations of sub-machines.
http://hypatia.stanford.edu/hp/

Visual Turing
http://apolo.cs.pub.ro/~cheran/vturing/

References:

Harry R. Lewis, Christos H. Papadimitriou Elements of the Theory of Computation, second edition, Upper Saddle River, N.J.: Prentice-Hall, 1998.

R. Gregory Taylor, Models of Computation and Formal Languages, 1998 Oxford University Press.

Steven Gutz, Up to Speed With Swing: User Interfaces With Java Foundation Classes, Greenwich, CT.: Manning, 1998.

Bruce Eckel, Thinking in Java, Upper Saddle River, N.J.: Prentice-Hall, 1998.