class GNFA(FA)

Classes and methods for working with generalized non-deterministic finite automata.

GNFA

Bases: FA

The GNFA class is a subclass of FA and represents a generalized nondeterministic finite automaton.

Its main usage is for conversion of DFAs and NFAs to regular expressions. Note that because of this, the GNFA doesn't support any binary operators or reading input (e.g. read_input_stepwise). Every GNFA can be rendered natively inside of- a Jupyter notebook (automatically calling show_diagram without any arguments) if installed with the visual optional dependency. Note that input_str cannot be set as an argument to show_diagram, as the GNFA does not read input.

Except for initial_state and final_state, one transition goes from every state to every other state, and also from each state to itself. To accommodate this, transitions can be regular expressions and None, in addition to normal input symbols.

Parameters:

Name	Type	Description	Default
states	AbstractSet[GNFAStateT]	Set of the GNFA's valid states.	required
input_symbols	AbstractSet[str]	Set of the GNFA's valid input symbols, each of which is a singleton string.	required
transitions	Mapping[GNFAStateT, Mapping[GNFAStateT, Optional[str]]]	A dict with the transitions for each state, except final_state. Each key is a state name and each value is dict which maps a state (the key) to the transition expression (the value) or None. The transition expression is a regular expression (string) over input_symbols, and the following symbols only: *, |, ?, (). This is a subset of the standard regular expressions using this package.	required
initial_state	GNFAStateT	The initial state for this GNFA. Has transitions going to every other state, but no transitions coming in from any other state.	required
final_state	GNFAStateT	A single final state for this GNFA. Has transitions coming in from every other state, but no transitions going to any other state. Must be different from the initial_state.	required

from_dfa(target_dfa) classmethod

Initialize this GNFA as one equivalent to the given DFA.

Parameters:

Name	Type	Description	Default
target_dfa	DFA	The DFA to construct an equivalent GNFA for.	required

Returns:

Type	Description
Self	The GNFA accepting the language of the input DFA.

from_nfa(target_nfa) classmethod

Initialize this GNFA as one equivalent to the given NFA.

Parameters:

Name	Type	Description	Default
target_nfa	NFA	The NFA to construct an equivalent GNFA for.	required

Returns:

Type	Description
Self	The GNFA accepting the language of the input NFA.

iter_transitions()

Iterate over all transitions in the GNFA. Each transition is a tuple of the form (from_state, to_state, symbol).

Returns:

Type	Description
Generator[Tuple[GNFAStateT, GNFAStateT, str], None, None]	The desired generator over the GNFA transitions.

to_regex()

Convert GNFA to regular expression.

Returns:

Type	Description
str	A regular expression equivalent to the input GNFA.

validate()

Raises an exception if this automaton is not internally consistent.

Raises:

Type	Description
InvalidStateError	If this GNFA has invalid states in the transition dictionary.
MissingStateError	If this GNFA has states missing from the transition dictionary.
InvalidRegexError	If this GNFA has invalid regex in the transition dictionary.