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