In 1997, Java became stable and widely available. The features
of Java that captured our attention were that Java is platform independent,
has a core graphical library, is multi-threaded language and is strongly
object oriented. I was interested in understanding object oriented
programming and Professor Lander was interested in getting a graphical
simulation tool. We decided that I should develop a suite of recognizers,
one for each category of languages, with the same look and feel. The goal
was to make the programs as intuitive as possible to use and the programs
should reinforce the formal definitions.
To reinforce the formal definitions the students can only input the
definitions of the recognizers via a text file. To promote intuitive
use, all recognizers have the same type starting frame with the same pull
down menu commands. A graphical bar for controlling the execution
of the simulations is the same for all recognizers. To speed grading
a text version for each recognizer is also provided.
DFA //type
example 1 -- Recognizes strings of even numbers of 0's and 1's
//title
0 1 // input alphabet
q0 q1 q2 q3 // machine states
q0 // initial state
q0 // final states
q0 0 q2 // transition: input state, input
symbol, output state
q0 1 q1
q1 0 q3
q1 1 q0
q2 0 q0
q2 1 q3
q3 0 q1
q3 1 q2
end //required
For detail description on executing a DFA see finite
state machine documentation in the appendix. The documentation
includes five examples from Hopcroft and Ullman's, Introduction to Automata
Theory, Languages and Computation, 1979. Some additional
features of the simulator is any single character can be an element in
S. The state names can be any string.
Since finite state machines are guaranteed to terminate with accept/not
accept the program will also terminate. The simulation can run forwards
and backwards in steps controlled by user or in various continuous speeds.
The user can interrupt the execution with new input or can restart
the FSM with current input.
The classic definition of a deterministic one-tapeTuring machine is:
a 7-tuple M = { S,
G, ^, Q, s, A, d
} where
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
Because of the non deterministic nature of this automaton addition features
were added to the display. Since it is impossible to predict the
correct execution branch during the simulation, upon a successful termination
the user can view the correct execution sequence. Also at every
step the user can examine every active branch. See the appendix for
further examples and more details on executing the program.
This software was developed on a Windows 95 platform using just the Java supplied JDK. It has been tested on a Sparc workstations and works without modification.
The Controller class object, controls the speed and direction of the simulation, is a very general code that is used unchanged (except for package name) in the three applications. The code for the running of the simulation are in a separate class, XQTThread and is slightly different for each recognizer. The simulations are run in a synchronized while loop. The thread of the simulation terminates either by the automaton failing or the automaton recognizing the string. The non deterministic pushdown automaton's thread terminates after the history is completed. To allow the simulation to run in reverse an instance of the class java.util.Stack is used to remember previous states. Instances of Controller class and XQTThread are only needed to run the graphical option of the simulators.
The MainFrame class is the blank initial controlling frame. Each simulator has slightly different supporting classes to display the graphics. This was the hardest part to develop since much experimenting with the different displays was required. The primary programming technique used to display the graphics was double buffering.
The TextDriver class is the top driver for the running the text
option. TextDriver gets the file names and then "runs" the
simulation. Since there is no graphics there doesn't need to be two
user threads.
The MachineDescriptionXXX (XXX for each type of machine) class is used to read from file the machine description and return a "machine". This code is used by both the graphics option and the text option.
The machine package has many classes. The XXXMachine class
is the main class for storing the state of the machine. Functions
and relations for storing the transitions use the class java.util.Hashtable.
There are separate classes for building sets of states and symbols.
User defined exceptions are used to communicate with the "controlling"
objects that there are no more transitions.
AbstractMachineSingletonFactory: The purpose of this class is to access a family of dependent objects, machine, xqtThread and displayPanel without specifying their concrete classes. Only one object of each type is need during a single simulation and the AbstractMachineSingletonFactory is the keeper of the references to these objects. See AbstractSingletonFactory code in the next section that discusses some features about the code..
The concrete classes TuringMachineFactory, FiniteMachineFactory and PDAMachineFactory know how to read a bufferReader and build the appropriate objects.ControlBarSingleton: The controlBarSingleton allows the user to control the speed and executing direction of the simulation. There is only one bar during the entire execution. However, the threads being control can be changed dynamically by sending ControlBarSingleton.setXqtThread ( XQTThread ) message. See the details of this code in the next section.
Memento: The purpose of Memento is to encapsulate
a snapshot of the state of the machine including the position of
the input tape, current machine state, output and other necessary data.
For non deterministic machines the memento will be a vector of this
information.
DisplayPanel : The purpose of displayPanel
is to graphically display the current state of the machine when
it is requested by the xqtThread. DisplayPanel
also has a java.awt.Textfield for interactive input of strings to
be run by the machine.
import java.awt.*;
import java.awt.event.*;
/**
* The ControlBarSingleton class
*
* @author E F Head
* @version 2, 98/4/15
* @since JDK1.1.5
*/
/** ControlBarSingleton is a panel used to control
* the speed and direction of the XQTThread.
* This is a Singleton.
**/
public class ControlBarSingleton extends Panel {
static private final ControlBarSingleton controller_
= new ControlBarSingleton ();
private static XQTThread xqt;
static public ControlBarSingleton getControlBarHandle()
{
return controller_;
}
static public void setXQTThread(XQTThread x) {
xqt = x;
}
// Set the number of micro controls to 5
static final int NoCONTROLS = 5;
static final Color THISWAY = Color.green;
static final Color OTHERWAY = Color.gray;
final Label backwardLabel = new Label ("<<");
final Label forwardLabel = new Label (">>",Label.RIGHT);
final CButton headBackwardButton = new CButton();
final CButton headForewardButton = new CButton();
final Button stepF = new Button("Step>");
final Button stepB = new Button ("<Step");
final Button stop = new Button("Stop");
private boolean xqtNotStarted_ = true;
/**
* Create a <code> ControlBarSingleton </code>
* object to control a <code> XQTThread
</code> object.
*/
final ControlBarSingleton ( ) {
int speed = 1;
backwardLabel.setFont(new Font("Helvetica",Font.BOLD,24));
forwardLabel.setFont(new Font("Helvetica",Font.BOLD,24));
backwardLabel.setForeground(OTHERWAY);
forwardLabel.setForeground(THISWAY);
add(backwardLabel);
CButton b = new CButton();
// lowest speed back control button
CButton lowN = null; // lower
control speed
CButton highN = null; // higher
control speed
// Create a "linklist" of control
buttons
// forward and backward speed controls
for (int i=0; i< NoCONTROLS ;
i++) {
add(b);
lowN = (i==NoCONTROLS-2)?
headBackwardButton:
(i==NoCONTROLS-1)?
null : new CButton();
b.lowerNeighbor(lowN);
b.higherNeighbor(highN);
// add eventlistener
speed++
final int speedF
= speed++;
final CButton
bF = b;
b.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent e){
if (xqtNotStarted_) {
xqtNotStarted_ = false;
xqt.start();
}
synchronized(xqt) {
xqt.notify();
bF.eventPressed();
xqt.backward(speedF*200);
}
backwardLabel.setForeground(THISWAY);
forwardLabel.setForeground(OTHERWAY);
headForewardButton.setOFF();
}
}
);
highN = b;
b = lowN;
}// for loop
// Head of forward and backwards
control
stepB.setFont(new Font ("Helvetica",
Font.PLAIN, 20));
stepB.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent e){
if (xqtNotStarted_) {
xqtNotStarted_ = false;
xqt.start();
}
backwardLabel.setForeground(THISWAY);
forwardLabel.setForeground(OTHERWAY);
headForewardButton.setOFF();
headBackwardButton.setOFF();
synchronized(xqt) {
xqt.notify();
xqt.backwardStep();
}
}
}
);
add(stepB); // <STEP
stop.setFont(new Font ("Helvetica",
Font.PLAIN, 20));
stop.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent e){
backwardLabel.setForeground(OTHERWAY);
forwardLabel.setForeground(OTHERWAY);
headForewardButton.setOFF();
headBackwardButton.setOFF();
xqt.pause();
}
}
);
add(stop); // STOP
stepF.setFont(new Font ("Helvetica",
Font.PLAIN, 20));
stepF.addActionListener(
new
ActionListener(){
public void actionPerformed(ActionEvent e){
if (xqtNotStarted_) {
xqtNotStarted_ = false;
xqt.start();
}
backwardLabel.setForeground(OTHERWAY);
forwardLabel.setForeground(THISWAY);
headForewardButton.setOFF();
headBackwardButton.setOFF();
synchronized (xqt) {
xqt.notify();
xqt.forwardStep();
}
}
}
);
add(stepF); // STEP>
b = headForewardButton;
lowN = null;
speed = NoCONTROLS;
for (int i=0; i<NoCONTROLS; i++)
{
add(b);
b.higherNeighbor(
highN = (i==NoCONTROLS)?null:new CButton());
b.lowerNeighbor(lowN);
final int speedF
= speed--;
final CButton
bF = b;
b.addActionListener(
new ActionListener(){
public void actionPerformed(ActionEvent e){
if (xqtNotStarted_) {
xqtNotStarted_ = false;
xqt.start();
}
bF.eventPressed();
synchronized (xqt) {
xqt.notify();
}
xqt.forward(speedF*200);
backwardLabel.setForeground(OTHERWAY);
forwardLabel.setForeground(THISWAY);
headBackwardButton.setOFF();
}
}
);
lowN = b;
b = highN;
}// for i <NoCONTROLS
add(forwardLabel);
setVisible(false);
disableControls();
}
/**
* Prevent the <code>ControlBarSingleton</code> object
from
* reacting to user button presses.
*/
public void disableControls() {
backwardLabel.setForeground(OTHERWAY);
forwardLabel.setForeground(OTHERWAY);
headForewardButton.setOFF();
headBackwardButton.setOFF();
headForewardButton.disableCButton();
headBackwardButton.disableCButton();
stepB.setEnabled(false);
stepF.setEnabled(false);
repaint();
}
/**
* Set the micro controls of <code>ControlBarSingleton</code>
* object that handle the control for going in reverse
* to be able to react to user button presses.
*/
public void enableReverseControls() {
backwardLabel.setForeground(OTHERWAY);
headBackwardButton.enableCButton();
stepB.setEnabled(true);
repaint();
}
/**
* Set the <code>ControlBarSingleton</code> object to
be able
* to react to user button presses.
*/
public void enableControls() {
backwardLabel.setForeground(OTHERWAY);
forwardLabel.setForeground(THISWAY);
stepB.setEnabled(true);
stepF.setEnabled(true);
headForewardButton.enableCButton();
headBackwardButton.enableCButton();
repaint();
}
/**
* Prevent the micro controls of the
* <code>ControlBarSingleton</code> object that
* handle reversing from reacting to user button presses.
*/
public void disableReverse() {
backwardLabel.setForeground(OTHERWAY);
headBackwardButton.setOFF();
stepB.setEnabled(false);
forwardLabel.setForeground(OTHERWAY);
headBackwardButton.disableCButton();
headForewardButton.setOFF();
repaint();
}
public void stopReverse() {
backwardLabel.setForeground(OTHERWAY);
headBackwardButton.setOFF();
repaint();
}
static final Color OFF = Color.gray;
static final Color ON = Color.red;
/** private Inner classes to construct a custom button
*/
private static final class CButton
extends Button {
protected CButton higherNeighbor_ = null;
protected CButton lowerNeighbor_ = null;
CButton () {
super(".");
setBackground(OFF);
}
CButton (String l) {
super(l);
setFont(new Font ("Helvetica", Font.BOLD,
24) );
setBackground(OFF);
}
void higherNeighbor (CButton b) {
higherNeighbor_ = b;
}
void lowerNeighbor (CButton b) {
lowerNeighbor_ = b;
}
public void eventPressed () {
setBackground(ON);
if (higherNeighbor_ != null){
higherNeighbor_.setOFF();
}
if (lowerNeighbor_ != null){
lowerNeighbor_.setON();
}
}
void setON() {
setBackground(ON);
if (lowerNeighbor_ != null){
lowerNeighbor_.setON();
}
repaint();
}
void disableCButton() {
setEnabled(false);
if (higherNeighbor_ != null){
higherNeighbor_.disableCButton();
}
}
void setOFF() {
setBackground(OFF);
if (higherNeighbor_ != null){
higherNeighbor_.setOFF();
}
repaint();
}
void enableCButton() {
setBackground(OFF);
setEnabled(true);
if(higherNeighbor_ != null){
higherNeighbor_.enableCButton();
}
}
public void update(Graphics g) {
paint(g);
}
} // end of CButton
}
package singleton;
/**
* AbstractSingletonFactory exists to return a handle
* to two abstract Products. For illustration the two Product
* classes are an inner class, but they could be a
top level class.
* The extended Concrete classes will create a
* concrete Product whose handle is obtainable through
* AbstractSingletonFactory.getHandle1
( )
* AbstractSingletonFactory.getHandle2
( )
*
*/
abstract public class AbstractSingletonFactory {
private static Product single1_;
private static Product2 single2_;
protected AbstractSingletonFactory() { }
/**
* Allow inherited class to set our reference
to a Product
*/
protected static void setHandle1(Product s) {
System.out.println("Abstract Product: setHandle1()");
single1_ = s;
}
protected static void setHandle2(Product2 s) {
System.out.println("Abstract Product: setHandle2()
");
single2_ = s;
}
/**
* Every object can get a reference to the same
Product object.
*/
static public Product getHandle1()
throws NotSetException {
if (single1_ == null) {
System.out.println("
No Product:: getHandle1() ");
throw new NotSetException();
} else {
return single1_;
}
}
static public Product2 getHandle2()
throws NotSetException {
if (single2_ == null) {
System.out.println("
No Product2 exists");
throw new NotSetException();
} else {
return single2_;
}
}
/**
* Just to illustrate would normally be a top
level class
*/
static public abstract class Product {
public Product () {
System.out.println("
Product constructor ");
}
}
static public abstract class Product2 {
public Product2 () {
System.out.println("
Product2 constructor ");
}
}
}
package singletonC;
import singleton.*;
/**
* Knows how to make a concrete produce and will set the single
product
* object in the parent class, AbstractSingletonFactory.
*/
public class ConcreteFactory
extends AbstractSingletonFactory
{
private ConcreteFactory() { }
/**
* Creates Product object.
*/
static public void createProducts() {
setHandle1( new AbstractSingletonFactory.Product()
{
public String toString() {
return "Concrete Product1!";
}
}
);
setHandle2( new AbstractSingletonFactory.Product2()
{
public String toString() {
return "Concrete Product2!";
}
}
);
}
protected static void setHandle1 (Product p) {
AbstractSingletonFactory.setHandle1(p);
}
protected static void setHandle2 (Product2 p) {
AbstractSingletonFactory.setHandle2(p);
}
}
package singletonC;
import singleton.*;
/**
* Just a driver to test the Factory Singleton Pattern
**/
public class Main {
static public void main (String [] a ) {
AbstractSingletonFactory.Product
s=null;
AbstractSingletonFactory.Product2
s2=null;
ConcreteFactory.createProducts();
try {
s = AbstractSingletonFactory.getHandle1();
} catch (NotSetException x) {
System.err.println("No
Product available");
}
try {
s2 = AbstractSingletonFactory.getHandle2();
} catch (NotSetException x) {
System.err.println("No
Product available");
}
}
}
