CAVE User's Guide

This document is intended to provide a basic introduction to the CAVE applet. It describes the features of CAVE, as well as its current limitations. I have done my best to make this guide a comprehensive one, but there are bound to be omissions; if you find that you have a question which this guide does not answer to your satisfaction, please feel free to contact me at mtashbook@acm.org.

Binaries and a working demonstration version of the CAVE applet are available from the CAVE home page.

The latest version of this document can always be found online at:

http://www.cs.virginia.edu/~mst2f/caveguide.html.

The CAVE Applet Interface
Entering and Clearing DFAs
Manipulating DFAs
Submitting Input Strings to DFAs
Tutor Mode
Limitations of CAVE
Planned Improvements
Version History

The CAVE Applet Interface

Upon loading the CAVE applet, you will see the main CAVE interface:

This interface contains four main sections. From top to bottom, left to right, they are:

The main display area
The string input area
The computation control area
The DFA entry area

The main display area is used to present information and feedback to the user. The contents of this area are never erased; you can always use the scrollbar to examine the history of your current session using CAVE. When the CAVE applet first appears, this region contains a very brief set of instructions for using the applet.

The string input area, in the upper right corner of the CAVE applet interface, is used to test input strings for acceptance by the entered DFAs. This region is described below (see Submitting Input Strings to DFAs).

The computation control area is used to manipulate DFAs within CAVE. This region contains a drop-down menu where you can select an operation (see the Manipulating DFAs section below) to perform. After selecting an operation from the menu, use the "Evaluate" button to actually perform the computation.

This region of the applet interface also contains a checkbox to enable (or disable) Tutor mode. Tutor mode is described below, in its own section.

The DFA entry area allows users to load DFAs into CAVE. In general, CAVE users will start by using this region. Users can enter up to two DFAs at a time. DFAs are entered into CAVE as transition tables.

The right side of this region will display a partial transition table for DFAs that are constructed by CAVE. Due to space constraints, this region will only display the first eight rows of a constructed DFA's transition table.

The current design of the CAVE applet interface allows users to enter DFAs with up to six states and two input symbols (for a total of twelve transitions per DFA). This restriction is the result of the current design of the interface; the underlying Java code can support DFAs of virtually any size, and DFAs that are constructed as the result of a computation can have far more than six states.

Entering and Clearing DFAs

DFAs can be entered into CAVE using the DFA entry area at the bottom of the applet interface. CAVE represents DFAs internally as transition tables, and expects DFAs to be entered in the same way. Limitations imposed by the applet interface restrict entered DFAs to no more than six states and two input symbols (by convention, 'a' and 'b'). Only the leftmost two transition tables are available for input; the rightmost transition table is used to display (part of) the results of a DFA computation.

For each DFA, CAVE provides a grid of text entry boxes. This grid comprises the transition table for that DFA. To enter a DFA, fill in the appropriate transition table entries. You do not have to fill in every row of the table, but you must completely fill in the transition table rows for all of the states of your DFA. States are numbered beginning with 0, and state 0 is always treated as the initial state.

To the left of the transition table, you will find a column of checkboxes. Each checkbox corresponds to a different DFA state. These checkboxes are used to indicate whether a particular DFA state is a final state. If the box is checked, then the corresponding DFA state will be final (+).

When you have finished entering the values for a transition table (and setting final states), click the appropriate "Enter DFA" button. Each DFA has its own pair of buttons to submit or erase the DFA. CAVE will examine the input; if there are no errors or problems (for example, missing table entries or non-numeric table entries), then CAVE will construct the DFA and print out its transition table in the display area at the top of the applet. If there are any errors or omissions in your transition table, then CAVE will produce an error message and indicate where the problem lies in the transition table.

You may erase or clear a DFA at any time by using the appropriate "Clear DFA" button. Clearing a DFA will erase the transition table and remove the DFA from memory. CAVE will not display a message to confirm whether you really want to erase your DFA, so you should be extremely careful with this feature!

Manipulating DFAs

CAVE currently supports five basic DFA operations:

Complement
Intersection
Kleene closure
Product (Concatenation)
Union

These operations can be selected from the drop-down menu just below CAVE's display area. To perform an operation on one or both of the source DFAs, click once on the "Evaluate" button to the right of the drop-down menu. CAVE will then display the results of the operation in the display area, and fill in the appropriate rows of the transition table display in the lower right corner of the applet.

If you have not defined the DFA (or DFAs) required for a particular computation (for example, if you want CAVE to produce the complement of DFA 2, but you have not yet entered a transition table for DFA 2), CAVE will produce an error message.

If you have enabled Tutor mode (see below), the CAVE display area will show additional details of the computation before presenting the result. Otherwise, CAVE will only display the final result of the computation.

At the moment, CAVE does not support "chaining" computations (for example, taking the union of two DFAs, and then taking the intersection of that union DFA with a third DFA). If you wish to perform a series of computations, you will need to perform individual computations, and submit the results of previous computations as new source DFAs. In the example situation given above, you would begin by entering DFAs 1 and 2, and taking their union. You would then erase DFA 1 and replace it with the transition table of the union DFA, and replace DFA 2 with DFA 3 before taking their intersection. This limitation is scheduled to be addressed in the next version of CAVE.

Submitting Input Strings to DFAs

In addition to combining and manipulating DFAs, you can also submit input strings to those DFAs to test for acceptance (or rejection). When you submit an input string for testing, CAVE will test that string with each currently defined DFA. For example, if you have already performed one or more DFA manipulations, then CAVE will test your input string against DFA 1, DFA 2, and DFA 3 (the result DFA). For each DFA, CAVE will display a message indicating whether the input string was accepted or rejected by that DFA.

The upper right corner of the CAVE applet interface contains a text input area. Use this text entry field to enter your input string. When you are finished, click the button marked "Test String" to submit your input string to each of the currently-defined DFAs.

Keep in mind that, for the moment, CAVE DFAs only support two alphabet symbols (a and b).

Tutor Mode

Normally, CAVE displays only the results of its computations. For example, if you submit two DFAs to CAVE and apply the union (FA1 + FA2) operation, CAVE will display the transition table of the resulting union DFA. Sometimes, however, it can be difficult to see exactly how or why CAVE produced a particular machine as the result of a computation.

In response to this problem, CAVE offers a feature called "Tutor mode." Tutor mode can be enabled through a checkbox just below the main display area. When CAVE is in Tutor mode, the display area will show the progress of the constructive algorithm as CAVE performs the desired operation. CAVE will also present a brief overview of the algorithm being used.

Tutor mode is available for the union, product (concatenation), Kleene closure, and intersection operations. At present, Tutor mode does not provide any additional information when CAVE is constructing the complement of a DFA.

Limitations of CAVE

While CAVE currently works well, it has several significant limitations, most of which should be fixed in the very near future. Some of these limitations are listed below.

CAVE relies heavily on text-based input, in the form of transition tables. The ability to enter DFAs by "drawing" them would make the applet easier to use for beginning theory students (CAVE's target audience).
The current version of CAVE only offers text-based output; the program does not display any graphical representation of the source DFAs, or of the DFAs that it generates. This feature would also improve the pedagogical nature of the applet for beginning students; while a transition table may convey identical information, the pictorial representation is often easier for students to understand.
CAVE does not offer any way to perform a series of computations where each computation depends upon the results of prior computations. There is no way to "chain" several operations together. The current workaround for this is for the user to enter the new source DFA by hand, and then to perform the next computation in the series.
Users cannot enter transition tables for DFAs with more than six states, or with more than two input symbols. This limitation is due to the current size of the applet interface; CAVE can theoretically support DFAs of any size.
CAVE only works with DFAs; it does not handle other types of machines (like NFAs or PDAs; Turing Machines are handled separately by TCELL).

Planned Improvements

There are a number of improvements planned for future versions of CAVE. Many of these improvements are cosmetic, and deal primarily with the applet's interface, but others require the underlying Java code to be modified. These proposed changes are presented below in no particular order.

Add the ability to enter DFAs by drawing them as state diagrams. This would make CAVE easier to use for beginning computer theory students.
Redesign the CAVE interface to allow users to enter DFAs with more than two input symbols. This restriction is mostly due to the current design of the user interface, which does not have sufficient room to display wider transition tables. Within the CAVE applet itself, there is no such limitation on the number of input symbols that can be accepted by a particular DFA.
Allow the user to replace a source DFA with the results of a previous computation. This would allow users to more easily "chain" several computations together.
Expand CAVE to support other types of machines besides DFAs (for example, NFAs and PDAs). This is a long-term project, and will probably result in CAVE being divided into a series of related modules.

Version History

Version Date Description of Changes

1.0 1/2000 The very first Java version of CAVE (prior to this, there was a rudimentary test version of CAVE which was written in C++).

1.0.1 3/2000 Fixed a small bug in the setFinal() method of the DFA class (some changes during development led to an "off by one" error in some methods).

Fixed a bug where large DFAs (those with more than 7 states) were not initialized properly.

1.1 3/2000 Added "Tutor mode" to show students how several computations are performed. This feature is also nice for debugging (which is how the idea first appeared, as "verbose logging").

1.2 6/2000 Implemented Kleene closure, and expanded the applet window to accommodate a transition table display area for result DFAs. Added a text input area for testing input strings.

1.2.1 7/2000 Fixed a silly error of omission in the product computation code. If state X0 is a final DFA state, then state Z0 must correspond not only to X0, but also to Y0 (the initial state of DFA Y). That wasn't being done, until the code was corrected. A note to that effect was also added to the text for "Tutor mode."

1.2.2 4/2001 Fixed a boneheaded logic error in the DFA.parseString() method. This error meant that (a) FAs would often accept strings that caused the FA to end up in a non-final state, and (b) FAs could not handle the empty string (epsilon) if it was passed in as input.

Back to the CAVE Home Page | Back to my home page

This document was last updated on February 27, 2004 by Michael S. Tashbook (mtashbook@acm.org).

Version	Date	Description of Changes
1.0	1/2000	The very first Java version of CAVE (prior to this, there was a rudimentary test version of CAVE which was written in C++).
1.0.1	3/2000	Fixed a small bug in the `setFinal()` method of the DFA class (some changes during development led to an "off by one" error in some methods). Fixed a bug where large DFAs (those with more than 7 states) were not initialized properly.
1.1	3/2000	Added "Tutor mode" to show students how several computations are performed. This feature is also nice for debugging (which is how the idea first appeared, as "verbose logging").
1.2	6/2000	Implemented Kleene closure, and expanded the applet window to accommodate a transition table display area for result DFAs. Added a text input area for testing input strings.
1.2.1	7/2000	Fixed a silly error of omission in the product computation code. If state X0 is a final DFA state, then state Z0 must correspond not only to X0, but also to Y0 (the initial state of DFA Y). That wasn't being done, until the code was corrected. A note to that effect was also added to the text for "Tutor mode."
1.2.2	4/2001	Fixed a boneheaded logic error in the DFA.parseString() method. This error meant that (a) FAs would often accept strings that caused the FA to end up in a non-final state, and (b) FAs could not handle the empty string (epsilon) if it was passed in as input.