Package pyxb :: Package binding :: Module nfa :: Class FiniteAutomaton

Class FiniteAutomaton

object --+    
         |    
      dict --+
             |
            FiniteAutomaton

Represent a finite automaton.

The FiniteAutomaton instance is a map from states to sets of transitions.

A transition is a map from a key to a set of states.

States are integers. The start and end state are distinguished. Transitions are by value, and are one of ElementDeclaration, ModelGroup[all], and Wildcard. The value None represents an epsilon transition.

Instance Methods

[hide private]

new empty dictionary

__init__(self)
x.__init__(...) initializes x; see x.__class__.__doc__ for signature

source code

newState(self)
Create a new node in the automaton.

source code

start(self)
Obtain the start node of the automaton.

source code

end(self)
Obtain the end node of the automaton.

source code

addTransition(self, key, source, destination)
Add a transition on key from the source state to the destination state.

source code

ok(self, key, source, destination)
Return True iff the automaton can transition from source to destination on key.

source code

addSubAutomaton(self, nfa)
Copy the given automaton into this one.

source code

alphabet(self)
Determine the keys that allow transitions in the automaton.

source code

isFullPath(self, steps)
Return True iff the automaton can be traversed from start to end following the given steps, including arbitrary epsilon moves.

source code

move(self, states, key)
Determine the set of states reachable from the input set of states by one key transition.

source code

epsilonClosure(self, states)
Calculate the epsilon closure of the given set of states.

source code

reverseTransitions(self)

source code

minimizeDFA(self, final_states)

source code

buildDFA(self)
Build a deterministic finite automaton that accepts the same language as this one.

source code

__str__(self)
str(x)

source code

Inherited from dict: __cmp__, __contains__, __delitem__, __eq__, __ge__, __getattribute__, __getitem__, __gt__, __hash__, __iter__, __le__, __len__, __lt__, __ne__, __new__, __repr__, __setitem__, clear, copy, fromkeys, get, has_key, items, iteritems, iterkeys, itervalues, keys, pop, popitem, setdefault, update, values