Class Npda

java.lang.Object
  extended by Npda

public class Npda
extends java.lang.Object

An Npda object models a nondeterministic pushdown automaton(npda). Please see the book An Introduction to Formal Languages and Automata, by Peter Linz, for a detailed description of npdas.

An Npda object has the capability of reading an npda from a text file. An example of the format of an npda text file is as follows (this file accepts the language a^n b^n for n>=0):

transitions
Q0 Q1 a Z 1Z
Q1 Q1 a 1 11
Q1 Q2 L 1 1
Q2 Q2 b 1 L
Q2 Q3 L Z Z
finalStates
Q0 Q3

The file consists of two sections: (i) a section listing the npda's transitions, which starts with a line consisting of the string "transitions"; (ii) a section listing the npda's final states, which starts with a line consisting of the string "finalStates".

The transitions section specifies one transition per line. Each transition is specified by five strings separated by whitespace. The five strings represent, respectively: (i) the label of the state where the transition begins; (ii) the label of the state where the transition ends; (iii) the symbol read from the input string; (iv) the symbol popped from the stack; (v) the symbol(s) pushed onto the stack. The initial state of the npda is hardwired as "Q0". Conventionally, the other states are named "Q1", "Q2" etc., but this is not enforced. The string alphabet, stack alphabet, and list of labels for the npda are not defined explicitly; rather, they are defined to be everything that is encountered in the transitions section of the npda file.

Three special symbols are defined: 'Z' is the stack start symbol; 'L' represents lambda, the empty symbol; and 'I' represents an illegal symbol i.e. a symbol that is not in the string alphabet or stack alphabet (this illegal symbol does not form part of the usual definition of an npda, but can be useful for implementing an npda).

It is suggested that the string alphabet consists only of lowercase letters, and the stack alphabet consists only of the digits 0-9 (and Z). However, this suggestion is not enforced.

The finalStates section consists of a single line (in addition to the line marking the start of the section). This line contains a sequence of strings separated by whitespace, where each string is the name of a label that is a final state of the npda.


Field Summary
static char ILLEGAL
          Special symbol representing an illegal symbol -- see the class documentation for more discussion of this.
static java.lang.String INITIAL_STATE
          The label of the initial state of the npda.
static char LAMBDA
          Special symbol representing the empty symbol
static char STACK_START
          Special symbol representing the stack start symbol
 
Constructor Summary
Npda()
          Create a new, empty npda object
 
Method Summary
 boolean accepts(java.lang.String input)
          Return true if this npda accepts the given string, and false otherwise.
static void main(java.lang.String[] args)
           
 void readFromFile(java.lang.String filename)
          Read a description of the npda from a file.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

INITIAL_STATE

public static final java.lang.String INITIAL_STATE
The label of the initial state of the npda.

See Also:
Constant Field Values

LAMBDA

public static final char LAMBDA
Special symbol representing the empty symbol

See Also:
Constant Field Values

STACK_START

public static final char STACK_START
Special symbol representing the stack start symbol

See Also:
Constant Field Values

ILLEGAL

public static final char ILLEGAL
Special symbol representing an illegal symbol -- see the class documentation for more discussion of this.

See Also:
Constant Field Values
Constructor Detail

Npda

public Npda()
Create a new, empty npda object

Method Detail

readFromFile

public void readFromFile(java.lang.String filename)
                  throws java.io.FileNotFoundException,
                         NpdaException
Read a description of the npda from a file. Please see the documentation of the npda class for a description of the file format.

Parameters:
filename - the name of the file to be read
Throws:
java.io.FileNotFoundException - if the file isn't found
NpdaException - if the contents of the file does not represent a legal npda

accepts

public boolean accepts(java.lang.String input)
Return true if this npda accepts the given string, and false otherwise.


main

public static void main(java.lang.String[] args)