|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.ObjectNpda
public class Npda
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 |
---|
public static final java.lang.String INITIAL_STATE
public static final char LAMBDA
public static final char STACK_START
public static final char ILLEGAL
Constructor Detail |
---|
public Npda()
Method Detail |
---|
public void readFromFile(java.lang.String filename) throws java.io.FileNotFoundException, NpdaException
filename
- the name of the file to be read
java.io.FileNotFoundException
- if the file isn't found
NpdaException
- if the contents of the file does not
represent a legal npdapublic boolean accepts(java.lang.String input)
public static void main(java.lang.String[] args)
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |