Package pylilac :: Module DelegateFSA :: Class DelegateFSA

Class DelegateFSA

FiniteStateAutomaton --+
                       |
                      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

S, a finite set of states
Λ, a set of label which can accept tokens from the set Σ
s ∈ S, the start state
F ⊆ S, the set of final states
δ: S × (Λ∪{ε}) → S*, transition function

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).

δ: S × Λ → 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
Inherited from FiniteStateAutomaton
	`__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)`

Generated by Epydoc 2.1 on Sat Aug 26 09:33:46 2006

http://epydoc.sf.net