Class Dfa

java.lang.Object
  extended by Dfa

public class Dfa
extends java.lang.Object

A Dfa object models a discrete finite automaton (dfa). Please see the book An Introduction to Formal Languages and AutomataI, by Peter Linz, for a detailed description of dfas.

A Dfa object has the capability of reading a dfa from a text file. An example of the format of a dfa text file is:

transitions
Q0 a Q1
Q0 b Q2
Q1 a Q1
Q1 b Q2
Q2 a Q3
Q2 b Q3
Q3 a Q2
Q3 b Q2
finalStates
Q1 Q3

The file consists of two sections: (i) a section listing the dfa's transitions, which starts with a line consisting of the string "transitions"; (ii) a section listing the dfa'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 three strings separated by whitespace. The three strings represent, respectively, the label of the state where the transition begins, the symbol that triggers the transition (which must consist of a single character), and the label of the state to which the transition moves the dfa. The initial state of the dfa is hardwired as "Q0". Conventionally, the other states are named "Q1", "Q2" etc., but this is not enforced. The alphabet and list of labels for the dfa are not defined explicitly; rather, they are defined to be everything that is encountered in the transitions section of the dfa file.

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 dfa.


Field Summary
static java.lang.String INITIAL_STATE
          The label of the initial state of the dfa.
 
Constructor Summary
Dfa()
          Create a new, empty dfa object
 
Method Summary
 boolean accepts(java.lang.String string)
          Return true if this dfa 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 dfa 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 dfa.

See Also:
Constant Field Values
Constructor Detail

Dfa

public Dfa()
Create a new, empty dfa object

Method Detail

readFromFile

public void readFromFile(java.lang.String filename)
                  throws java.io.FileNotFoundException,
                         DfaException
Read a description of the dfa from a file. Please see the documentation of the Dfa object 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
DfaException - if the contents of the file does not represent a legal dfa

accepts

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


main

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