org.opentripplanner.routing.automata

Class NFA

java.lang.Object

org.opentripplanner.routing.automata.NFA

Direct Known Subclasses:

DFA

public class NFA
extends Object

Field Summary

Fields

Modifier and Type	Field and Description
Set<AutomatonState>	acceptStates
Nonterminal	nt the nonterminal which this state machine accepts
Set<AutomatonState>	startStates

Constructor Summary

Constructors

Modifier	Constructor and Description
	NFA(Nonterminal nt)
protected	NFA(Nonterminal nt, boolean build)

Method Summary

Modifier and Type	Method and Description
DFA	minimize() Convert to a minimal DFA using Brzozowski's algorithm: reverse the transitions and apply the powerset construction, yielding a minimal DFA for the reverse language, then repeat the procedure to get a minimal DFA for the original language.
protected void	relabelNodes()
NFA	reverse()
DFA	toDFA()
String	toGraphViz()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

nt

public final Nonterminal nt

the nonterminal which this state machine accepts

startStates

public final Set<AutomatonState> startStates

acceptStates

public final Set<AutomatonState> acceptStates

Constructor Detail

NFA

public NFA(Nonterminal nt)

NFA

protected NFA(Nonterminal nt,
              boolean build)

Method Detail

toDFA

public DFA toDFA()

reverse

public NFA reverse()

minimize

public DFA minimize()

Convert to a minimal DFA using Brzozowski's algorithm: reverse the transitions and apply the powerset construction, yielding a minimal DFA for the reverse language, then repeat the procedure to get a minimal DFA for the original language.

toGraphViz

public String toGraphViz()

relabelNodes

protected void relabelNodes()