python_fsa.nfa

A nondeterministic finite state machine and its corresponding transducer

Classes

`NFA`(*, states, alphabet, initial, ...[, epsilon])	A nondeterministic finite state machine.
`NFATransducer`(initial, transitions, final, ...)	A mutable Moore machine that accepts inputs one at a time.

class NFA(*, states: Iterable[S], alphabet: Iterable[T], initial: S, transitions: Mapping[tuple[S, T], Iterable[S]], final: Iterable[S], epsilon: object = 'ε')

Bases: Generic[T, S]

A nondeterministic finite state machine.

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

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

EPSILON: Final[str] = 'ε'

states: Final[frozenset[S]]

alphabet: Final[frozenset[T]]

initial: Final[S]

final: Final[frozenset[S]]

epsilon: Final[object]

transitions: Final[Mapping[tuple[S, T], frozenset[S]]]

accepts(input: Iterable[T]) → bool: Returns True if the given input is accepted by this NFA and False otherwise

to_dfa() → DFA[T, frozenset[S]]: Transforms this NFA into a DFA

without_epsilon() → NFA[T, S]: Returns a new NFA with epsilon transitions removed. Any unreachable states as a result of this are also removed.

transducer(output: Mapping[S, V] = None) → NFATransducer[T, S, V]: Returns a transducer with the given output mapping. By default, this maps states to a boolean indicating whether the closure of that state contains an accepting/final state.

class NFATransducer(initial: Iterable[S], transitions: Mapping[tuple[S, T], frozenset[S]], final: frozenset[S], output: Mapping[S, V])

Bases: Generic[T, S, V]

A mutable Moore machine that accepts inputs one at a time. The output of each “state” is the set of the mapping S -> V for all states, S, in the current state set.

Allows for the NFA transitions to be a partial function – in the case a transition is not defined, the state and output become the empty set.

property current: frozenset[S]: The current state set of the transducer

property output: frozenset[V]: The current output set of the transducer

property is_accepting: bool: Returns True if the transducer is in an accepting state

push(input: T) → frozenset[V]: Transitions the transducer and returns the new output set