Package nltk_lite :: Package contrib :: Package mit :: Package six863 :: Package kimmo :: Module fsa :: Class FSA
[hide private]
[frames] | no frames]

Class FSA

source code

     object --+    
              |    
yaml.YAMLObject --+
                  |
                 FSA

A class for finite state automata. In general, it represents nondetermnistic finite state automata, with DFAs being a special case.

Nested Classes [hide private]

Inherited from yaml.YAMLObject: __metaclass__, yaml_dumper, yaml_loader

Instance Methods [hide private]
 
__init__(self, sigma='', transitions=None, start=0, finals=None)
Set up the FSA.
source code
 
_build_reverse_transitions(self) source code
 
generate_transitions(self)
A generator that yields each transition arrow in the FSA in the form (source, label, target).
source code
 
labels(self, s1, s2)
A generator for all possible labels taking state s1 to state s2.
source code
 
sigma(self)
The alphabet of the FSA.
source code
 
alphabet(self)
The alphabet of the FSA.
source code
 
check_in_sigma(self, label)
Check whether a given object is in the alphabet.
source code
 
__len__(self)
The number of states in the FSA.
source code
int
new_state(self)
Add a new state to the FSA.
source code
 
add_state(self, name) source code
 
start(self)
Returns: the ID of the FSA's start state.
source code
set
finals(self)
Returns: the IDs of all accept states.
source code
set
nonfinals(self)
Returns: the IDs of all accept states.
source code
list
states(self)
Returns: a list of all states in the FSA.
source code
 
add_final(self, state)
Make a state into an accept state.
source code
 
delete_final(self, state)
Make an accept state no longer be an accept state.
source code
 
set_final(self, states)
Set the list of accept states.
source code
 
set_start(self, start)
Set the start state of the FSA.
source code
 
in_finals(self, list)
Check whether a sequence contains any final states.
source code
 
insert_safe(self, s1, label, s2) source code
 
insert(self, s1, label, s2)
Add a new transition to the FSA.
source code
 
_add_transition(self, map, s1, label, s2) source code
 
_del_transition(self, map, s1, label, s2) source code
 
delete(self, s1, label, s2)
Removes a transition from the FSA.
source code
 
delete_state(self, state)
Removes a state and all its transitions from the FSA.
source code
set
incident_transitions(self, state)
Returns: a set of transitions into or out of a state.
source code
 
relabel_state(self, old, new)
Assigns a state a new identifier.
source code
 
next(self, state, symbol)
The set of states reached from a certain state via a given symbol.
source code
 
nextStates(self, state, symbol)
The set of states reached from a certain state via a given symbol.
source code
 
move(self, states, symbol)
The set of states reached from a set of states via a given symbol.
source code
 
is_deterministic(self)
Return whether this is a DFA (every symbol leads from a state to at most one target state).
source code
 
nextState(self, state, symbol)
The single state reached from a state via a given symbol.
source code
 
forward_traverse(self, state)
All states reachable by following transitions from a given state.
source code
 
reverse_traverse(self, state)
All states from which a given state is reachable by following transitions.
source code
 
_forward_accessible(self, s1, visited) source code
 
_reverse_accessible(self, s1, visited) source code
 
prune(self)
Modifies an FSA to remove inaccessible states and unused transitions.
source code
 
_clean_map(self, map) source code
 
accessible(self) source code
set
e_closure(self, states)
Given a set of states, return the set of states reachable from those states by following epsilon transitions.
source code
 
dfa(self)
Return a DFA that is equivalent to this FSA.
source code
 
generate(self, maxlen, state=0, prefix='')
Generate all accepting sequences of length at most maxlen.
source code
 
pp(self)
Print a representation of this FSA (in human-readable YAML format).
source code
 
show_pygraph(self, title='FSA', outfile=None, labels=True, root=None) source code
 
__str__(self)
str(x)
source code

Inherited from object: __delattr__, __getattribute__, __hash__, __new__, __reduce__, __reduce_ex__, __repr__, __setattr__

Class Methods [hide private]
 
from_yaml(cls, loader, node)
Convert a representation node to a Python object.
source code
 
to_yaml(cls, dumper, data)
Convert a Python object to a representation node.
source code
Class Variables [hide private]
  yaml_tag = '!FSA'

Inherited from yaml.YAMLObject: yaml_flow_style

Properties [hide private]

Inherited from object: __class__

Method Details [hide private]

__init__(self, sigma='', transitions=None, start=0, finals=None)
(Constructor)

source code 

Set up the FSA.

Parameters:
  • sigma (sequence) - the alphabet of the FSA
  • transitions (dict) - A dictionary representing the states and transitions in the FSA. The keys are state identifiers (any hashable object), and the values are dictionaries that map input symbols to the sets of states they lead to.
  • start (hashable object) - The identifier of the start state
  • finals (sequence) - The identifiers of the accept states
Overrides: object.__init__

new_state(self)

source code 

Add a new state to the FSA.

Returns: int
the ID of the new state (a sequentially-assigned number).

start(self)

source code 
Returns:
the ID of the FSA's start state.

finals(self)

source code 
Returns: set
the IDs of all accept states.

nonfinals(self)

source code 
Returns: set
the IDs of all accept states.

states(self)

source code 
Returns: list
a list of all states in the FSA.

insert(self, s1, label, s2)

source code 

Add a new transition to the FSA.

Parameters:
  • s1 - the source of the transition
  • label - the element of the alphabet that labels the transition
  • s2 - the destination of the transition

delete(self, s1, label, s2)

source code 

Removes a transition from the FSA.

Parameters:
  • s1 - the source of the transition
  • label - the element of the alphabet that labels the transition
  • s2 - the destination of the transition

incident_transitions(self, state)

source code 
Returns: set
a set of transitions into or out of a state.

nextState(self, state, symbol)

source code 

The single state reached from a state via a given symbol. If there is more than one such state, raises a ValueError. If there is no such state, returns None.

e_closure(self, states)

source code 

Given a set of states, return the set of states reachable from those states by following epsilon transitions.

Parameters:
  • states (sequence) - the initial set of states
Returns: set
a superset of the given states, reachable by epsilon transitions

from_yaml(cls, loader, node)
Class Method

source code 

Convert a representation node to a Python object.

Overrides: yaml.YAMLObject.from_yaml
(inherited documentation)

to_yaml(cls, dumper, data)
Class Method

source code 

Convert a Python object to a representation node.

Overrides: yaml.YAMLObject.to_yaml
(inherited documentation)

__str__(self)
(Informal representation operator)

source code 

str(x)

Overrides: object.__str__
(inherited documentation)