class NFA(FA)

Classes and methods for working with nondeterministic finite automata.

NFA

Bases: FA

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

Every NFA has the same five DFA properties: state, input_symbols, transitions, initial_state, and final_states. However, the structure of the transitions object has been modified slightly to accommodate the fact that a single state can have more than one transition for the same symbol. Therefore, instead of mapping a symbol to one end state in each sub-dict, each symbol is mapped to a set of end states.

Every NFA can be rendered natively inside of a Jupyter notebook (automatically calling show_diagram without any arguments) if installed with the visual optional dependency.

Parameters:

Name	Type	Description	Default
states	AbstractSet[NFAStateT]	Set of the NFA's valid states.	required
input_symbols	AbstractSet[str]	Set of the NFA's valid input symbols, each of which is a singleton string.	required
transitions	Mapping[NFAStateT, Mapping[str, AbstractSet[NFAStateT]]]	Dict consisting of the transitions for each state. Each key is a state name, and each value is another dict which maps a symbol (the key) to a set of states (the value).	required
initial_state	NFAStateT	The initial state for this NFA.	required
final_states	AbstractSet[NFAStateT]	A set of final states for this NFA.	required

concatenate(other)

Given two NFAs, M1 and M2, which accept the languages L1 and L2 respectively, returns an NFA which accepts the language L1 concatenated with L2.

Parameters:

Name	Type	Description	Default
other	NFA	The NFA we want to concatenate with.	required

Returns:

Type	Description
Self	An NFA accepting the language concatenation of the two input NFAs.

edit_distance(input_symbols, reference_str, max_edit_distance, *, insertion=True, deletion=True, substitution=True) classmethod

Constructs the Levenshtein NFA for the given reference_str and given Levenshtein distance. This NFA recognizes strings within the given Levenshtein distance (commonly called edit distance) of the reference_str. Parameters control which error types the NFA will recognize (insertions, deletions, or substitutions). At least one error type must be set.

If insertion and deletion are False and substitution is True, then this is the same as Hamming distance.

If insertion and deletion are True and substitution is False, then this is the same as LCS distance.

insertion, deletion, and substitution all default to True.

Code adapted from: http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the NFA over.	required
reference_str	str	The reference string the NFA will use to recognize other close strings.	required
max_edit_distance	int	The maximum edit distance from the reference string this NFA will recognize. Must be positive.	required
insertion	bool	Whether to recognize insertion edits relative to the reference string.	True
deletion	bool	Whether to recognize deletion edits relative to the reference string.	True
substitution	bool	Whether to recognize substitution edits relative to the reference string.	True

Returns:

Type	Description
Self	An NFA accepting all strings within the given edit distance to the reference string.

Raises:

Type	Description
ValueError	Raised if the max_edit_distance is negative or all of the error flags are set to False (at least one must be True).

eliminate_lambda()

Returns an equivalent NFA with lambda transitions removed.

Returns:

Type	Description
Self	The equivalent NFA with lambda transitions removed.

from_dfa(target_dfa) classmethod

Initialize this NFA as one equivalent to the given DFA.

Parameters:

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

Returns:

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

from_regex(regex, *, input_symbols=None) classmethod

Initialize this NFA as one equivalent to the given regular expression.

Parameters:

Name	Type	Description	Default
regex	str	The regex to construct an equivalent NFA for.	required
input_symbols	Optional[AbstractSet[str]]	The set of input symbols to create the NFA over. If not set, defaults to all ascii letters and digits.	None

Returns:

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

intersection(other)

Given two NFAs, M1 and M2, which accept the languages L1 and L2 respectively, returns an NFA which accepts the intersection of L1 and L2.

Parameters:

Name	Type	Description	Default
other	NFA	The NFA we want to take an intersection with.	required

Returns:

Type	Description
Self	An NFA accepting the intersection of the two input NFAs.

iter_transitions()

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

Returns:

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

kleene_star()

Given an NFA which accepts the language L, returns an NFA which accepts L repeated 0 or more times.

Returns:

Type	Description
Self	An NFA accepting the finite repetition of the input NFA.

left_quotient(other)

Given two NFAs, M1 and M2, which accept the languages L1 and L2 respectively, returns an NFA which accepts the left quotient of L1 with respect to L2 (L2 L1).

Construction is based off of the one described here: https://cs.stackexchange.com/a/102043

Parameters:

Name	Type	Description	Default
other	NFA	The NFA we want to take a left quotient with.	required

Returns:

Type	Description
Self	An NFA accepting the left quotient of the two input NFAs.

option()

Given an NFA which accepts the language L, returns an NFA which accepts L repeated 0 or 1 times.

Returns:

Type	Description
Self	An NFA accepting the optional of the input NFA.

read_input_stepwise(input_str)

Return a generator that yields the configuration of this NFA at each step while reading input.

Parameters:

Name	Type	Description	Default
input_str	str	The input string to read.	required

Yields:

Type	Description
Generator[AbstractSet[NFAStateT], None, None]	A generator that yields the current configuration (a set of states) of the NFA after each step of reading input.

Raises:

Type	Description
RejectionException	Raised if this NFA does not accept the input string.

reverse()

Given an NFA which accepts the language L, returns an NFA which accepts the reverse of L.

Returns:

Type	Description
Self	An NFA accepting the reversal of the input NFA.

right_quotient(other)

Given two NFAs, M1 and M2, which accept the languages L1 and L2 respectively, returns an NFA which accepts the right quotient of L1 with respect to L2 (L1 / L2).

Construction is based off of the one described here: https://cs.stackexchange.com/a/102043

Parameters:

Name	Type	Description	Default
other	NFA	The NFA we want to take a right quotient with.	required

Returns:

Type	Description
Self	An NFA accepting the right quotient of the two input NFAs.

shuffle_product(other)

Given two NFAs, M1 and M2, which accept the languages L1 and L2 respectively, returns an NFA which accepts the shuffle of L1 and L2.

Parameters:

Name	Type	Description	Default
other	NFA	The NFA we want to take a shuffle product with.	required

Returns:

Type	Description
Self	An NFA accepting the shuffle product of the two input NFAs.

union(other)

Given two NFAs, M1 and M2, which accept the languages L1 and L2 respectively, returns an NFA which accepts the union of L1 and L2.

Parameters:

Name	Type	Description	Default
other	NFA	The NFA we want to take a union with.	required

Returns:

Type	Description
Self	An NFA accepting the union of the two input NFAs.

validate()

Raises an exception if this automaton is not internally consistent.

Raises:

Type	Description
InvalidStateError	If this NFA has invalid states in the transition dictionary.
MissingStateError	If this NFA has states missing from the transition dictionary.
InvalidSymbolError	If this NFA has invalid symbols in the transition dictionary.