laser.regularlanguage.util
Class GNFA<L extends LabelInterface>

java.lang.Object
  extended by laser.regularlanguage.util.GNFA<L>
Type Parameters:
L - The type of labels used by the FSAs and REs

public class GNFA<L extends LabelInterface>
extends java.lang.Object

The GNFA class represents a generalized nondeterministic finite automaton (GNFA). A GNFA is an NFA with alphabet A where the transitions are annotated with regular expressions (REs) from A* instead of just labels from A. See lemma 1.32 in "Introduction to the Theory of Computation" (Michael Sipser, pp 69 - 76, 1997)

Author:
Heather M. Conboy (laser-software@cs.umass.edu)

Field Summary
protected  StringAlphabetFactory alphabetFactory_
          The AlphabetFactoryInterface to be used to create alphabets and labels
protected  NFAtoDFAConverter<L> determinizer_
          Creates deterministic FSAs (DFAs)
protected  RunnableFSAInterface<L> fsa_
          The FSA to be converted to a GNFA
protected  StringFSAFactory fsaFactory_
          The FSAFactoryInterface to be used to create FSAs
protected  MutableFSA<StringLabel> gnfa_
          The corresponding GNFA in special form
protected  Minimizer<L> minimizer_
          Creates minimial DFAs
protected  REFactory<L> reFactory_
          The REFactory to be used to create REs
protected  RLFactory<L> rlFactory_
          The RLFactory to be used to convert between RE and FSA args
 
Constructor Summary
GNFA(RunnableFSAInterface<L> fsa, REFactory<L> reFactory, RLFactory<L> rlFactory)
          Creates the GNFA that corresponds to the given FSA.
 
Method Summary
 AlphabetInterface<StringLabel> getAlphabet()
          Gets the alphabet of this GNFA.
 java.lang.String getName()
          Gets the name of this GNFA.
 RE<L> getRE()
          Gets the RE that corresponds to this GNFA.
 void toDot(java.io.File outFile)
          Outputs this GNFA in dot format to the given File.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

alphabetFactory_

protected final StringAlphabetFactory alphabetFactory_
The AlphabetFactoryInterface to be used to create alphabets and labels


fsaFactory_

protected final StringFSAFactory fsaFactory_
The FSAFactoryInterface to be used to create FSAs


determinizer_

protected NFAtoDFAConverter<L extends LabelInterface> determinizer_
Creates deterministic FSAs (DFAs)


minimizer_

protected Minimizer<L extends LabelInterface> minimizer_
Creates minimial DFAs


reFactory_

protected final REFactory<L extends LabelInterface> reFactory_
The REFactory to be used to create REs


rlFactory_

protected final RLFactory<L extends LabelInterface> rlFactory_
The RLFactory to be used to convert between RE and FSA args


fsa_

protected final RunnableFSAInterface<L extends LabelInterface> fsa_
The FSA to be converted to a GNFA


gnfa_

protected final MutableFSA<StringLabel> gnfa_
The corresponding GNFA in special form

NOTES:

  1. The start state is non-accepting, has no incoming transitions, and has outgoing transitions to every other state.
  2. The accept state is not the start state, has incoming transitions from every other state, and has no outgoing transitions.
  3. Every other state has a transition to every other state (including one self-loop transition to itself) but not including the start state.

Each transition is an FSALabelPatternTransitionInterface with an RELabelPattern associated with it.

In practice, each pair of states has zero or one transition(s) between them. If there is no transition, then it represents an implicit empty transition, else it represents an explicit non-empty transition.

Constructor Detail

GNFA

public GNFA(RunnableFSAInterface<L> fsa,
            REFactory<L> reFactory,
            RLFactory<L> rlFactory)
Creates the GNFA that corresponds to the given FSA.

PRECONDITIONS:

Parameters:
fsa - The FSA to be converted
reFactory - The REFactory to be used to create new REs (non-null)
rlFactory - The RLFactory to be used to convert from RE to FSA args (non-null)
Method Detail

getName

public java.lang.String getName()
Gets the name of this GNFA.

Returns:
The name

getAlphabet

public AlphabetInterface<StringLabel> getAlphabet()
Gets the alphabet of this GNFA.

Returns:
The alphabet

getRE

public RE<L> getRE()
                                   throws REException
Gets the RE that corresponds to this GNFA.

NOTE: The RE is not guaranteed to be "minimal".

Returns:
The corresponding RE
Throws:
REException - if the RE cannot be retrieved from this GNFA

toDot

public void toDot(java.io.File outFile)
           throws java.io.IOException
Outputs this GNFA in dot format to the given File.

Parameters:
outFile - The File to use as output (non-null)
Throws:
java.io.IOException - if an I/O error occurs