Package pylilac :: Module FiniteStateAutomaton :: Class FiniteStateAutomaton
[frames | no frames]

Class FiniteStateAutomaton

Known Subclasses:
DelegateFSA

A Finite-state Automaton, or Finite-state Machine (FSA). In general, it is a Nondeterministic Finite-state Automaton (NFA).

A Nondeterministic Finite-state Automaton is a tuple (S, Λ, s, F, δ) where A Deterministic Finite-state Automaton (DFA) is like NFA, except that the value of the transition function δ is a single state in S (instead of a subset of S).

Types of parameters

The structure is designed to support different data types, even though states are usually numbers and input tokens are characters.

In basic operations S and Λ must support equivalence and hashing.

For determinization, S must support comparability.

For recognition, Λ must also support callability.
Method Summary
  __init__(self)
Create an empty FSA (∅, Λ, None, ∅, ∅):
  __call__(self, start, token)
  __delitem__(self, start_label_end)
  __getitem__(self, start, label)
  __repr__(self)
  __setitem__(self, start_label, end)
  add_state(self, state)
  add_transition(self, start, label, end)
Defines a new association δ(start, label) → end.
  determinized(self)
frozenset epsilon_closure(self, states)
Evaluates ε-closure(states).
  get_final(self)
  get_initial(self)
  get_transitions(self, start, label)
Evaluate ...
  minimized(self)
  next_states(self, start, token)
Evaluate δ(start, label).
  parse(self, tokens)
  remove_state(self, state)
  remove_transitions(self, start, label, end)
  reversed(self)
  set_final(self, state)
  set_initial(self, state)
  states(self)
Return S, the states of the FSA.
  transitions_from(self, start)
Evaluate ...
  unset_final(self, state)

Method Details

__init__(self)
(Constructor)

Create an empty FSA (∅, Λ, None, ∅, ∅):

__call__(self, start, token)
(Call operator)

See Also: next_states

__delitem__(self, start_label_end)
(Index deletion operator)

See Also: remove_transitions

__getitem__(self, start, label)
(Indexing operator)

See Also: get_transitions

__setitem__(self, start_label, end)
(Index assignment operator)

See Also: add_transition

add_transition(self, start, label, end)

Defines a new association δ(start, label) → end.
Parameters:
start - An existing or new state, to be used as the start state.
label - A label for a new transition, or EPSILON for the ε label.
end - An existing or new state, to be used as the end state.

epsilon_closure(self, states)

Evaluates ε-closure(states).
Parameters:
states - A subset of the FSA states.
           (type=set)
Returns:
The ε-closure of the given set of states. The result is a frozen set.
           (type=frozenset)

get_transitions(self, start, label)

Evaluate ...
Parameters:
start - An existing state.
Returns:
...
Raises:
StateError - Fired if the state does not exist.

next_states(self, start, token)

Evaluate δ(start, label).
Parameters:
start - An existing state.
token - The token to match.
Returns:
A set of states reachable by the transitions having the given label.
Raises:
StateError - Fired if the state does not exist.

states(self)

Return S, the states of the FSA.

transitions_from(self, start)

Evaluate ...
Parameters:
start - An existing state.
Returns:
...
Raises:
StateError - Fired if the state does not exist.

Generated by Epydoc 2.1 on Sat Aug 26 09:33:46 2006 http://epydoc.sf.net