ANOTHER NON-DETERMINISTIC PUSH-DOWN AUTOMATON, IMPLEMENTED AS A JAVATM APPLICATION
Version 1.0 (January 20,1998)

TM Java is a registered trademark of Sun Microsystems

This simulator handles non-deterministic push-down automata and can simulate acceptance by final state or by empty stack.

Contents:


Obtaining the Java interpreter

Down-load the Java Development Kit using a browser (lynx, Internet explorer, Netscape), go to the site http://www.javasoft.com and select "Java Development Kit." You need to download the JDK1.1.5 or later for your machine, probably Microsoft's Windows 95/NT but various UNIX platforms support Java. If you are running Windows 3.1, you must go to the IBM site and look there: http://www.alphaworks.ibm.com (this site does not work usefully with lynx). For Windows 3.1 you are looking for IBM’s ADK for Java 1. 1 or later

From home, be prepared for several hours download time (try overnight).

The file is a self-extracting executable. It should install into the directory C:\jdk1.1.5 (or later). Check the installation notes if you are using IBM’s ADK.

If you plan to develop programs in Java, download the "api documentation" and unzip it using a 32-bit (long file name) "unzipper." Unzip to C:\ with directory options on; in this way it unzips to C:\jdk1.1.5\docs (or later). Also download the Java tutorial when you can (Binghamton students should let me know if they cannot find the tutorial.zip file). The tutorial has to be unzipped into the directory it will use, e.g., C:\jdk1.1.5\tutorial.


Obtaining the Finite State Machine simulator

NO file copying is necessary if you are working locally and using our server (bingsuns).

For your own PC, download the file pdasim_bgm.zip (Windows) or pdasim_bgm.tar (UNIX) and unzip from your root directory. These zip files include this document and the associated gif's. We recommend that you keep the files in the directories shown and add C:\classes your CLASSPATH variable, despite the current recommendation from Javasoft not to use a CLASSPATH. The files provided are:
 
classes/pda/control/Controller$1.class
classes/pda/control/Controller$2.class
classes/pda/control/Controller$3.class
classes/pda/control/Controller$4.class
classes/pda/control/Controller$5.class
classes/pda/control/Controller$CButton.class
classes/pda/control/Controller.class
classes/pda/control/GraphCanvas$CurrentStateColor.class
classes/pda/control/GraphCanvas$Edge.class
classes/pda/control/GraphCanvas$FinalNode.class
classes/pda/control/GraphCanvas$Node.class
classes/pda/control/GraphCanvas$StartFinalNode.class
classes/pda/control/GraphCanvas$StartNode.class
classes/pda/control/GraphCanvas.class
classes/pda/control/MainFrame$1.class
classes/pda/control/MainFrame$2.class
classes/pda/control/MainFrame$3.class
classes/pda/control/MainFrame$4.class
classes/pda/control/MainFrame.class
classes/pda/control/PDAMachineDescription.class
classes/pda/control/PDAMachinePanel$1.class
classes/pda/control/PDAMachinePanel$BranchButtonActionListener.class
classes/pda/control/PDAMachinePanel$InputActionListener.class
classes/pda/control/PDAMachinePanel.class
classes/pda/control/RunMachine.class
classes/pda/control/StackDraw.class
classes/pda/control/TapeDraw.class
classes/pda/control/TextDriver$InputData.class
classes/pda/control/TextDriver.class
classes/pda/control/Viewer.class
classes/pda/control/XQTThread.class
classes/pda/machine/
classes/pda/machine/AcceptException.class
classes/pda/machine/Alphabet.class
classes/pda/machine/EmptyPDAStackException.class
classes/pda/machine/EndOfInputException.class
classes/pda/machine/InputException.class
classes/pda/machine/InputTriple.class
classes/pda/machine/InternalException.class
classes/pda/machine/NotAcceptException.class
classes/pda/machine/NoTransitionException.class
classes/pda/machine/NotValidBranchException.class
classes/pda/machine/OutputTuple.class
classes/pda/machine/PDAMachine$EndOfInputException.class
classes/pda/machine/PDAMachine$InputTape.class
classes/pda/machine/PDAMachine.class
classes/pda/machine/PDAMachineException.class
classes/pda/machine/Relation$Enumerator.class
classes/pda/machine/Relation$InputTriple.class
classes/pda/machine/Relation.class
classes/pda/machine/Remember.class
classes/pda/machine/SetOfOutputTuples.class
classes/pda/machine/SetOfStates.class
classes/pda/machine/STACKandTapePos.class
classes/pda/machine/State.class
classes/GraderPDA.class
classes/PDA.class
pda_source/input1.txt
pda_source/input5.txt
pda_source/pda1.txt
pda_source/pda2.txt
pda_source/pda3.txt
pda_source/pda4.txt
pda_source/pda5.txt
pda_source/pda1.gif
pda_source/pda10.gif
pda_source/pda11.gif
pda_source/pda12.gif
pda_source/pda13.gif
pda_source/pda14.gif
pda_source/pda15.gif
pda_source/pda16.gif
pda_source/pda17.gif
pda_source/pda18.gif
pda_source/pda2.gif
pda_source/pda3.gif
pda_source/pda4.gif
pda_source/pda5.gif
pda_source/pda6.gif
pda_source/pda7.gif
pda_source/pda8.gif
pda_source/pda9.gif
pda_source/pdadoc.html

(the path shown is for UNIX, you get the equivalent on a WINDOWS machine)

Note that Java is case sensitive, even on directory names


Setting the environment

Open or create AUTOEXEC.BAT.

Add the following two lines after any other modification to the path

set path = %path%;c:\jdk1.1.5\bin

set CLASSPATH = c:\classes
Despite suggestions in the Java installation files, we find this CLASSPATH very convenient. On bingsuns you have to modify the file ".cshrc" to add the lines (check which is the latest jdk)
setenv PATH ${PATH}:/opt/local/java/jdk1.1.5/bin 

setenv CLASSPATH /u0/users/A/head/classes:<your login path>/classes

Obtaining the example files

The files obtained will be (you can also save them from the following links)  pda1.txt, pda2.txt, pda3.txt, pda4.txt, pda5.txt. The languages that these machines accept are annotated in the heading of the machine text and as the title of the Java frame that runs the simulation. When you download these files make sure there are no empty lines at the top of the file. They are included in the zip and tar files and will be placed in a subdirectory C:\pda_source.
The test files input1.txt (for pda1.txt), input5.txt (for pda5.txt), are used in conjunction with the text-only versions of the program, as described below.

Using the graphical version of the Simulator

When you type in the command window (MS-DOS window on Windows 95/NT and an X-Term window on Solaris) you will see the frame shown in Figure 1.

If you click on "Machine" in the Menu Bar, you pull down the options "New Machine" and "Restart," as shown in Figure 2.

When you click on "New Machine," you get a File Dialog Box, which allows you to open a file that contains a description of the finite state machine that you are about to test, see Figure 3.

You select and open the appropriate file. The format for the file is described later. The simulator will load and display the states of the machine and the transitions between the states, see Figure 4. If there are detectable errors in the format of your machine these will be reported in your command window. Resize the window to allow you to spread out the states in the black area on the screen. The states are distributed at random on the screen and you can drag them with the mouse to any location in the black area, Figure 5.

Next you should insert an input string. If you do not, the input will be assumed to be the empty string. To insert an input string, click in the empty text field next to the label "Input." Type in the input string, Figure 6, and click the button "Accept Input Tape" OR hit enter Figure 7.

The control bar allows you to proceed one step at a time (by pressing "Step") or run continuously at different speeds (by pressing one of the smaller buttons, which will show up red). See Figure 8.

Everytime the simulator has multiple choices for the next transition it creates sufficient branches to simulate all the choices. If a branch has no transitions and fails to accept, the branch becomes null.  The "Prev Branch" and  "Next Branch" allows you to display all current active branches.    Figure 9 displays the branch that assumes (mistakenly) we are at the end of the tape.  Figure 8 displays the branch that assumes (correctly)  we have passed the mid-point of the tape.   Figure 10 displays the branch that assumes (mistakenly) we have not reached the midpoint of the tape.

NOTES

The PDA simulator also allows you to introduce a "New Input," which is selected under "Options" on the menu bar, and to "Restart" the machine with the same input, which is selected under "Machine" on the menu bar. See Figure 13 and Figure 14

SPECIAL FEATURES OF THE PDA SIMULATIONS


The course-grader's quick-to-use version of the Simulator

When a course grader is presented with a large number of PDA  text files to check, one time saving approach is to run all the PDA's against a set of test inputs. The grader should prepare a file with a number of test cases, for example the file input1.txt shown below. The first line (300) is an upper limit on the number of steps that the simulation can run for [this is for uniformity with the Turing machine simulator, where machines might run for ever]. The second line (16) is the total number of test cases in the file. Lines 3 through 18 are the test cases. Line 3 is a blank line representing the empty string.
300
7

aaabbaaa
abab
aabbaaaabbaa
aa
baab
aaaaaaaaaaaabaaaaaaaa
To run the grader's version, type the following:
java GraderPDA
or
java GraderPDA input1.txt
or
java GraderPDA input1.txt dfa1.txt
If the command-line parameters are not provided, there will be prompts to ask for them.
In the example below, the grader is working in the directory "pda_source" and types in the name of the common set of test cases in the file input1.txt. Then there is a prompt for the next PDA to test. In this example, the machine file pda1.txt was used. The following lines give the test results: "YES" means the current input was accepted, "NO" means that the end of the current input was reached but the input was not accepted and "Machine exception, ..." indicates that the simulation was suspended before the end of the current input string because the necessary transition was not defined in the automaton (this third possibility is quite normal). After running the tests, allowing the grader to check whether the tests match the correct responses, the program asks for another PDA file to test (against the same test inputs) so that the grader can run through all the students' solutions to a specific problem.
CC:\pda_source>java GraderPDA
Enter Input File Name: input1.txt

TITLE: NEW MACHINE
Enter Machine FileName: pda1.txt

TITLE: Example 1: Hopcroft & Ullman's PDA for {ww^R : w in (a + b)*}
0 YES
1 YES
2 No more executing PDA threads
3 YES
4 YES
5 YES
6 No more executing PDA threads

Another Machine? Y/N : n

C:\pda_source>


Format of the PDA  file

The format for the PDA files is the following. There should be no blank lines:

Line 1: type of machine (PDA)
Line 2: name of the machine. For assignments use name(s) and question number
Line 3: FINAL STATE or EMPTY STACK.  Determines how the machine accepts string.
Line 4: all characters in the input alphabet, separated by spaces
Line 5: all characters in the stack alphabet, separated by spaces
Line 6: initial stack symbol.
Line 7: all the machine states.
Line 8: the initial state of the PDA machine
Line 9: all the final state(s) separated by spaces. The list could be empty.
Line 10: first of a list of transitions (see below)
Line 11: another transition

Line ?: last of the list of transitions
Last line: end. You must type the word "end" but it can be upper or lower case

The format of a transition is:

<state> <input tape symbol> <input stack symbol> <next-state> <output string of stack symbols>

where

Example 1:

PDA  // Type, note such comments are permitted at the end of the line
Example 1--Hopcroft & Ullman's PDA for {ww^R : w in (a + b)*}
FINAL STATE // Final State or Empty Stack, this line is not case-sensitive
a b // Input Alphabet
a b Z // The stack alphabet
Z // The stack start symbol
q0 q1 q2 // Machine states (strings): note: alphabet and states are CASE-SENSITIVE
q0 // Initial State
q2 // Set of Final States--can be empty, in which case the machine should accept by empty stack
q0 \ Z q2 Z
q0 a Z q0 aZ
q0 b Z q0 bZ
q0 a a q1 \
q0 a a q0 aa
q0 a b q0 ab
q0 b a q0 ba
q0 b b q0 bb
q0 b b q1 \
q1 b b q1 \
q1 a a q1 \
q1 \ Z q2 Z
end   // REQUIRED, this line is not case-sensitive
 



 Comments?