FSM simulator

ANOTHER FINITE STATE MACHINE (FSM) SIMULATOR, IMPLEMENTED AS A JAVA^TM APPLICATION
Version 1.2.1 (bug-fixes December 10, 1997)

^TM Java is a registered trademark of Sun Microsystems

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.4 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.4 (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.4\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.4\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 fsmsim_bgm.zip (Windows) or fsmsim_bgm.tar 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/FSM.class
classes/fsm/control/MachineDescriptionFSM.class
classes/fsm/control/MainFrame$1.class
classes/fsm/control/MainFrame$2.class
classes/fsm/control/MainFrame$3.class
classes/fsm/control/MainFrame$4.class
classes/fsm/control/MainFrame.class
classes/fsm/display/CButton.class
classes/fsm/display/Controller$1.class
classes/fsm/display/Controller$2.class
classes/fsm/display/Controller$3.class
classes/fsm/display/Controller$4.class
classes/fsm/display/Controller$5.class
classes/fsm/display/Controller.class
classes/fsm/display/GraphCanvas$CurrentStateColor.class
classes/fsm/display/GraphCanvas$Edge.class
classes/fsm/display/GraphCanvas$FinalNode.class
classes/fsm/display/GraphCanvas$Node.class
classes/fsm/display/GraphCanvas$StartFinalNode.class
classes/fsm/display/GraphCanvas$StartNode.class
classes/fsm/display/GraphCanvas.class
classes/fsm/display/MachinePanel$1.class
classes/fsm/display/MachinePanel$InputActionListener.class
classes/fsm/display/MachinePanel.class
classes/fsm/display/TapeDraw.class
classes/fsm/display/TextDriver$InputData.class
classes/fsm/display/TextDriver.class
classes/fsm/display/Viewer.class
classes/fsm/machine/dfa/DFAMachine.class
classes/fsm/machine/dfa/Function$Enumerator.class
classes/fsm/machine/dfa/Function.class
classes/fsm/machine/nfa/NFAMachine.class
classes/fsm/machine/nfa/Relation$Enumerator.class
classes/fsm/machine/nfa/Relation.class
classes/fsm/machine/Alphabet.class
classes/fsm/machine/DefineRelationship.class
classes/fsm/machine/EndOfInputException.class
classes/fsm/machine/InputException.class
classes/fsm/machine/InputPair.class
classes/fsm/machine/InputTuple.class
classes/fsm/machine/Machine$InputTape.class
classes/fsm/machine/Machine.class
classes/fsm/machine/MachineException.class
classes/fsm/machine/OutputTuple.class
classes/fsm/machine/SetOfStates.class
classes/fsm/machine/State.class
classes/fsm/machine/Tuple.class
classes/fsm/xqt/RunMachine.class
classes/fsm/xqt/XQTThread.class
classes/DetailTextFSM.class
classes/GraderFSM.class
classes/QuickTextFSM.class
fsm_source/dfa1.txt
fsm_source/dfa2.txt
fsm_source/dfa3.txt
fsm_source/fsm1.gif
fsm_source/fsm10.gif
fsm_source/fsm11.gif
fsm_source/fsm12.gif
fsm_source/fsm13.gif
fsm_source/fsm14.gif
fsm_source/fsm15.gif
fsm_source/fsm2.gif
fsm_source/fsm3.gif
fsm_source/fsm4.gif
fsm_source/fsm5.gif
fsm_source/fsm6.gif
fsm_source/fsm7.gif
fsm_source/fsm8.gif
fsm_source/fsm9.gif
fsm_source/fsmdoc.html
fsm_source/inputd1.txt
fsm_source/inputd2.txt
fsm_source/inputd3.txt
fsm_source/inputn1.txt
fsm_source/nfa1.txt
fsm_source/nfa2.txt
fsm_source/nfa3.txt
fsm_source/nfa4.txt
fsm_source/nfa5.txt

(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.4\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.4/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) dfa1.txt, dfa2.txt, dfa3.txt, nfa1.txt, nfa2.txt, nfa3.txt, nfa4.txt, nfa5.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:\fsm_source.
The test files inputd1.txt, inputd2.txt, inputd3.txt, inputn1.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)

java FSM

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.

NOTES

The initial state is indicated by a green arrow
The final states are have an extra green oval around the state
The final states are also labeled in CAPITAL letters
There is a special feature that allows the machine to run in reverse, thereby undoing all the transitions that have occurred. Reverse execution is not possible after the machine halts (either in an accepting or a non-accepting state)
The number of transition steps executed so far is shown in a message next to the "Accept Input Tape" button
This message is replaced with an "ACCEPTED" or "Not accepted" message when the machine halts. Figure 8 shows the machine running, Figure 9 shows the machine when it accepts the input and Figure 10 shows the machine when it fails to accept an input
The command window will also show a final status message when the machine completes

The FSM 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 11 and Figure 12

SPECIAL NOTE ON NFA SIMULATIONS

In this version, the NFA simulation is really a demonstration of the DFA derived from the NFA. The states of this DFA are subsets of states of the NFA. The initial state appears as the epsilon-closure (lambda-closure) of the initial state, Figure 13. Each transition moves to a new set of states, taking the epsilon-closure (lambda-closure) each time, Figure 14. The input is accepted if the set contains a final state, Figure 15.

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

When a course grader is presented with a large number of FSM text files to check, one time saving approach is to run all the FSM's against a set of test inputs. The grader should prepare a file with a number of test cases, for example the file inputd1.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 
16 

11110101111110 
11110101111110111110 
101010 
1010100 
10101010 
000 
0000 
1010101010 
101010100 
11111111 
0 
00 
00000 
0110111 
01

To run the grader's version, type the following:

java GraderFSM

java GraderFSM inputd1.txt

java GraderFSM inputd1.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 "fsm_source" and types in the name of the common set of test cases in the file inputd1.txt. Then there is a prompt for the next FSM to test. In this example, the machine file dfa1.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 checking whether the tests match the correct responses, the program asks for another FSM file to test (against the same test inputs) so that the grader can run through all the solutions to a specific problem.

C:\fsm_source>java GraderFSM
Enter Input File Name: inputd1.txt

TITLE: NEW MACHINE
Enter Machine FileName: dfa1.txt

TITLE: DFA: Example 1--Eileen Head--Language: \ + 1* 0 1* 0 1* 0 + ... 
YES
YES
YES
YES
YES
YES
YES
YES
    MachineException: Input :Q4,1 has no next state
    MachineException: Input :Q4,0 has no next state
YES
NO
NO
    MachineException: Input :Q4,0 has no next state
NO
NO

Another Machine? Y/N

The short-form of the text-only version of the Simulator

A second text-only versions is designed to let a student work at an ASCII terminal, typically through a dial-up connection, which normally prevents the use of the GUI version. To run the simpler version, simply type one of the following:

java QuickTextFSM

java QuickTextFSM inputd1.txt

java QuickTextFSM inputd1.txt dfa1.txt

java QuickTextFSM inputd1.txt dfa1.txt logd1.txt

If the parameter "logd1.txt" is not provided, the default is "report.txt." If the other parameters are not provided, there will be prompts to request them. The file of test cases inputd1.txt is the same as before. The following example shows the use of the same FSM dfa1.txt, which was used above.

C:\fsm_source>java QuickTextFSM inputd1.txt

TITLE: NEW MACHINE
Enter Machine FileName: dfa1.txt

TITLE: DFA: Example 1--Eileen Head--Language: \ + ...
Ready? return

The program reports on whether the FSM accepted a particular input from the file inputd1.txt, in this case. The reports come in groups of 5. Examples include the following (the first example is a test with a blank input):

     INPUT:
  STATUS: DFA: Example 1--Eileen Head--Language: \ + 1* 0 1* 0 1* 0 + 
1* 0 1* 0 1* 0 1* 0 ACCEPTED after Step: 1
     INPUT: 11110101111110
  STATUS: DFA: Example 1--Eileen Head--Language: \ + 1* 0 1* 0 1* 0 + 
1* 0 1* 0 1* 0 1* 0 ACCEPTED after Step: 15
     INPUT: 00
  STATUS: DFA: Example 1--Eileen Head--Language: \ + 1* 0 1* 0 1* 0 + 
1* 0 1* 0 1* 0 1* 0 NOT Accepted after Step:3
     INPUT: 00000
 MachineException: Input :Q4,0 has no next state
     INPUT: 0110111
  STATUS: DFA: Example 1--Eileen Head--Language: \ + 1* 0 1* 0 1* 0 + 
1* 0 1* 0 1* 0 1* 0 NOT Accepted after Step:8

The same information shown on the screen is saved in the log file (default name: report.txt).

The full text-only version of the finite state machine simulator

For the text-only version, the FSM files are prepared in the same way as for the graphical version of the simulator. In this case, as before you need to prepare a file of inputs such as inputd1.txt. The file was described in the section on the Grader's version of the program. The results of the tests will be written to an output log, which has a default name is "report.txt" but can be modified by the user. This text-only can be run using one of the following choices:

java DetailTextFSM

java DetailTextFSM inputd1.txt

java DetailTextFSM inputd1.txt dfa1.txt

java DetailTextFSM inputd1.txt dfa1.txt logd1.txt

If the parameter "logd1.txt" is not provided, the default is "report.txt." If the other parameters are not provided, there will be prompts to request them. On the screen the results of each test are shown in exactly the same way as for the QuickTextFSM program described above (accept/reject/failure on account of a missing transition) with the name of the machine, the test input, the state where execution ended. The big difference is in the log file. Note that in this version, after each run of the simulator, you may also change the FSM, keeping the same input file (this feature is provided specifically for the grader who might be diagnosing the failure of students' work).

The format of the log file is shown in the following examples taken from dfa1.txt and inputd1.txt

TITLE: DFA: Example 1--Eileen Head--Language: \ + ... 
      INPUT: 
  SNAPSHOT:   START State:Q0
  SNAPSHOT:   Input Tapes:
  SNAPSHOT: 
  SNAPSHOT:  
  SNAPSHOT: Stopped ACCEPTED after Step: 1

      INPUT: 11110101111110
  SNAPSHOT:   START State:Q0
  SNAPSHOT:   Input Tapes:
  SNAPSHOT: 11110101111110
  SNAPSHOT:

  SNAPSHOT: Step number: 1,  Current State: Q0
  SNAPSHOT: 1110101111110

  SNAPSHOT: Step number: 2,  Current State: Q0
  SNAPSHOT: 110101111110

...

  SNAPSHOT: Step number: 13,  Current State: q2
  SNAPSHOT: 0

  SNAPSHOT: Step number: 14,  Current State: Q3
  SNAPSHOT: 
  SNAPSHOT: Stopped ACCEPTED after Step: 15

...

You can see the current state and remaining input at each step of the simulation. The file is a sequence of snapshots of the simulation, one for each cycle of the simulator program.

If the user does not get the expected result when viewing the on-screen report, the log file can be used to isolate which state/input combination caused the problem.

Format of the FSM file

The format for the DFA/NFA files is the following. There should be no blank lines:

Line 1: type of machine (DFA, NFA)
Line 2: name of the machine. For assignments use name(s) and question number
Line 3: all characters in the alphabet, separated by spaces
Line 4: the sates of the machine, separated by spaces
Line 5: the initial state of the DFA machine
Line 6: all the final state(s) separated by spaces. The list could be empty
Line 7: first of a list of transition (see below)
Line 8: 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:

where

the <state> and <next-state> are the names of states (strings with NO blanks).
the <input symbol> is a symbol from the "alphabet" or in the case of an NFA with an epsilon (lambda) transition, the symbol \ (a "backslash")

Example 1: NOTE THAT THE COMMENTS ON EACH LINE MUST HAVE A SPACE BEFORE THE SYMBOL "//"

DFA //Type, note such comments are permitted at the end of the line
Example 1--Hopcroft/Ullman--Language: {w in (0+1)* : #0's is even & #1's is even} //Title
0 1 // input alphabet, single symbols separated by spaces
q0 q1 q2 q3 // Machine states (strings): note: alphabet and states are CASE-SENSITIVE
q0 // the initial state, required--cannot be empty
q0 // final state(s)--can be empty, in which case language is empty
q0 0 q2 // transitions: input state, input symbol, output state
q0 1 q1 // do not forget there must be a space before the "slashes"
q1 0 q3
q1 1 q0
q2 0 q0
q2 1 q3
q3 0 q1
q3 1 q2
end //required, this line is not case-sensitive

Example 2 In the NFA, "\" signifies an empty transition

NFA //Type
Example--Les Lander //Title
a b // input alphabet, note such comments are permitted at the end of the line
q0 q1 q2 q3 q4 q5 q6 // Machine states
q0 // the initial state
q2 q4 // final state
q0 b q4 // transitions: input state, input symbol, output state
q0 \ q1 // epsilon (lambda) transition, "\" denotes lambda
q1 a q5
q1 b q2
q2 a q3
q2 \ q5
q3 b q2
q3 b q4
q3 \ q2
q4 b q6
q4 \ q2
q5 \ q0
q6 a q6
q6 \ q0
end //required

Comments?

ANOTHER FINITE STATE MACHINE (FSM) SIMULATOR, IMPLEMENTED AS A JAVATM APPLICATION Version 1.2.1 (bug-fixes December 10, 1997)

Contents: