python_fsa.dfa

A deterministic finite state machine and its corresponding transducer

Classes

DFA(*, alphabet, states, initial, ...)	A deterministic finite state machine.
DFATransducer(dfa, output)	A mutable Moore machine that accepts inputs one at a time.

class DFA(*, alphabet: Iterable[T], states: Iterable[S], initial: S, transitions: Mapping[tuple[S, T], S], final: Iterable[S])

Bases: Generic[T, S]

A deterministic finite state machine.

Allows for transitions to be a partial function – in the case a transition is not defined, the state becomes None.

DFAs are immutable and can only accept or reject whole sequences of tokens. However, a mutable DFATransducer can be constructed with the transducer() method which can accept one token at a time.

accepts(input: Iterable[T]) → bool

Returns True if the given input is accepted by this DFA and False otherwise

transducer(output: Mapping[S, V] = None) → DFATransducer[T, S, V]

Returns a transducer with the given output mapping. By default, this maps states to a boolean indicating whether that state is an accepting/final state.

squash() → DFA[T, str]

Converts all states to strings – any non-string iterables are joined to a string in sorted alphabetical order.

This is useful when wanting to render the DFA as graph.

class DFATransducer(dfa: DFA[T, S], output: Mapping[S, V])

Bases: Generic[T, S, V]

A mutable Moore machine that accepts inputs one at a time.

Allows for the DFA transitions to be a partial function – in the case a transition is not defined, the state and output become None, unless None is in the output domain.

property current: S

The current state of the transducer

property output: V

The current output of the transducer

property is_accepting: bool

Returns True if the transducer is in an accepting state

push(input: T) → V

Transitions the transducer and returns the new output