Package pylilac :: Module FiniteStateAutomaton :: Class FiniteStateAutomaton

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

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
	`__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