python_fsa

Deterministic and Nondeterministic finite state machines.

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 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] = 'ε'

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.