What is CAVE?

CAVE (the Constructive Algorithm Visualization Environment) was designed to illustrate the operation of several useful constructive algorithms (more on them in a moment) from computer theory. It is intended to serve as a teaching tool for computer theory instructors and students.

More specifically, CAVE implements constructive algorithms for building union, product (concatenation), and Kleene closure machines for DFAs (deterministic finite-state automata). CAVE can also produce the complement of a source DFA, and build an intersection machine for two source DFAs. These algorithms are called constructive because they actually build (construct) new DFAs (as opposed to algorithms which simply modify existing DFAs).

If DFA 1 accepts language L1, and DFA 2 accepts language L2, CAVE can construct DFAs to accept the following languages:

L1 + L2
L1L2 (L1 concatenated with L2)
L2L1 (L2 concatenated with L1)
L1* (the Kleene closure of L1)
L2* (the Kleene closure of L2)
L1' (the complement of L1)
L2' (the complement of L2)
L1 ∩ L2 (the intersection of L1 and L2)

Three of these constructive algorithms (union, product, and Kleene closure) are used in the proof of Kleene's theorem. Kleene's theorem states that finite-state automata, transition graphs, and regular languages are equivalent in terms of their expressive power. That is, any language that can be expressed by a regular language can also be expressed by some transition graph, and by some finite-state automaton.

CAVE's "Tutor mode"

CAVE features a special "tutor mode" setting. When the appropriate checkbox is selected, CAVE provides a running commentary on what it's doing. This allows students to observe the progress of a particular algorithm, and it explains how CAVE arrived at the result that it did.

How can I find out more about CAVE?

CAVE was written for an independent study project at Hofstra University. CAVE was also included as part of my master's thesis, A Constructive Approach For Visualizing Computer Theory. There is a paper that accompanies the CAVE applet; I will probably add a link to it in the near future.

CAVE is implemented as a Java applet; if your Web browser supports Java (and if you aren't using certain versions of Netscape Navigator), then you should see the applet at the bottom of this page. The CAVE interface should be somewhat self-explanatory. If you run into trouble, or have questions, please take a look at the CAVE user guide.

The binaries for CAVE can be downloaded using the link below (you may need to download a copy of Aladdin Systems' free Stuffit Expander to decompress the files). CAVE was developed and tested using Metrowerks CodeWarrior 5 and Apple's MRJ SDK 2.1.2, but it should work with any Java virtual machine/Web browser that supports Java 1.1.7 (or higher, I presume).

If you would like a copy of the CAVE source code to examine and/or modify, use the link at the bottom of the page to contact me.

Download the tarred and gzipped Java binaries for CAVE (includes this page and the user's guide)

Enough! On with the demo...

The CAVE demo applet should appear below in a Java-enabled browser (currently, Microsoft Internet Explorer 4.5 or higher -- for some reason, the applet does not work properly in Netscape Communicator 4.6 for Macintosh).

Oops! Either your browser is not capable of supporting Java applets, or something has gone wrong. Please turn on Java, or try a different Web browser; if neither of those options works, please send mail to mtashbook@acm.org, and I will try to fix the problem.

The CAVE User's Guide | Back to my home page