class DFA(FA)

Classes and methods for working with deterministic finite automata.

DFA

Bases: FA

The DFA class is a subclass of FA and represents a deterministic finite automaton.

Every DFA 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[DFAStateT]	Set of the DFA's valid states.	required
input_symbols	AbstractSet[str]	Set of the DFA's valid input symbols, each of which is a singleton string	required
transitions	Mapping[DFAStateT, Mapping[str, DFAStateT]]	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 state (the value).	required
initial_state	DFAStateT	The initial state for this DFA.	required
final_states	AbstractSet[DFAStateT]	A set of final states for this DFA	required
allow_partial	bool	By default, each DFA state must have a transition to every input symbol; if this parameter is True, you can disable this characteristic (such that any DFA state can have fewer transitions than input symbols). Note that a DFA must always have every state represented in the transition dictionary, even if there are no transitions on input symbols leaving a state (dictionary is left empty in that case).	True

cardinality()

Returns the cardinality of the language represented by the DFA.

Returns:

Type	Description
int	The cardinality of the language accepted by self.

Raises:

Type	Description
InfiniteLanguageException	Raised if self accepts an infinite language.

clear_cache()

Resets the word and count caches. Can be called if too much memory is being used.

complement(*, retain_names=False, minify=True)

Creates a DFA which accepts an input if and only if the old one does not. Minifies by default. Unreachable states are always removed. Partial DFAs are converted into complete ones.

Parameters:

Name	Type	Description	Default
retain_names	bool	Whether to retain state names through the complement and optional minify.	False
minify	bool	Whether to minify the result of the complement of the input DFA.	True

Returns:

Type	Description
Self	A DFA accepting the complement of the input DFA. State minimal by default.

count_mod(input_symbols, k, *, remainders=None, symbols_to_count=None) classmethod

Directly computes a DFA that counts given symbols and accepts all strings where the remainder of division by k is in the set of remainders given. The default value of remainders is {0} and all symbols are counted by default.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
k	int	The number to divide the length by.	required
remainders	Optional[AbstractSet[int]]	The remainders to accept. If set to None, defaults to {0}.	None
symbols_to_count	Optional[AbstractSet[str]]	The input symbols to count towards the length of words to accepts. If set to None, counts all symbols.	None

Returns:

Type	Description
Self	The DFA accepting the desired language.

count_words_of_length(k)

Returns count of words of length k accepted by the DFA.

Parameters:

Name	Type	Description	Default
k	int	The desired word length.	required

Returns:

Type	Description
int	The number of words of length k accepted by self.

difference(other, *, retain_names=False, minify=True)

Takes as input two DFAs M1 and M2 which accept languages L1 and L2 respectively. Returns a DFA which accepts the difference of L1 and L2.

Minifies by default. Unreachable states are always removed. If either input DFA is partial, the result is partial.

Parameters:

Name	Type	Description	Default
other	DFA	The DFA we want to take a difference with.	required
retain_names	bool	Whether to retain state names through the difference and optional minify.	False
minify	bool	Whether to minify the result of the difference of the two DFAs.	True

Returns:

Type	Description
Self	A DFA accepting the difference of the two input DFAs. State minimal by default.

empty_language(input_symbols) classmethod

Directly computes the minimal DFA rejecting all strings.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required

Returns:

Type	Description
Self	The DFA accepting the desired language.

from_finite_language(input_symbols, language, as_partial=True) classmethod

Directly computes the minimal DFA accepting the finite language given as input. Uses the algorithm described in Finite-State Techniques by Mihov and Schulz, Chapter 10

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
language	AbstractSet[str]	The language to accept.	required
as_partial	bool	Whether or not to construct this as a partial DFA.	True

Returns:

Type	Description
Self	The DFA accepting the desired language.

from_nfa(target_nfa, *, retain_names=False, minify=True) classmethod

Initialize this DFA as one equivalent to the given NFA. Note that this usually returns a partial DFA by default.

Parameters:

Name	Type	Description	Default
target_nfa	NFA	The NFA to construct an equivalent DFA for.	required
retain_names	bool	Whether or not to retain state names during processing.	False
minify	bool	Whether or not to minify the DFA resulting from the input NFA.	True

Returns:

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

from_prefix(input_symbols, prefix, *, contains=True, as_partial=True) classmethod

Directly computes the minimal DFA accepting strings with the given prefix. If contains is set to False then the complement is constructed instead.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
prefix	str	The prefix of strings that are accepted by this DFA.	required
contains	bool	Whether or not to construct the compliment DFA.	True
as_partial	bool	Whether or not to construct this DFA as a partial DFA.	True

Returns:

Type	Description
Self	The DFA accepting the desired language.

from_subsequence(input_symbols, subsequence, *, contains=True) classmethod

Directly computes the minimal DFA recognizing strings containing the given subsequence. If contains is set to False, then the complement is constructed instead.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
subsequence	str	The target subsequence of strings that are accepted by this DFA.	required
contains	bool	Whether or to construct the compliment DFA.	True

Returns:

Type	Description
Self	The DFA accepting the desired language.

from_substring(input_symbols, substring, *, contains=True, must_be_suffix=False) classmethod

Directly computes the minimal DFA recognizing strings containing the given substring. If contains is set to False then the complement is constructed instead. If must_be_suffix is set to True, then the substring must be a suffix instead.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
substring	str	The substring of strings that are accepted by this DFA.	required
contains	bool	Whether or to construct the compliment DFA.	True
must_be_suffix	bool	Whether or not the target substring must be a suffix.	False

Returns:

Type	Description
Self	The DFA accepting the desired language.

from_suffix(input_symbols, suffix, *, contains=True) classmethod

Directly computes the minimal DFA recognizing strings with the given suffix. If contains is set to False, then the complement is constructed instead.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
suffix	str	The suffix of strings that are accepted by this DFA.	required
contains	bool	Whether or not to construct the compliment DFA.	True

Returns:

Type	Description
Self	The DFA accepting the desired language.

intersection(other, *, retain_names=False, minify=True)

Takes as input two DFAs M1 and M2 which accept languages L1 and L2 respectively. Returns a DFA which accepts the intersection of L1 and L2.

Minifies by default. Unreachable states are always removed. If either input DFA is partial, the result is partial.

Parameters:

Name	Type	Description	Default
other	DFA	The DFA we want to take a intersection with.	required
retain_names	bool	Whether to retain state names through the intersection and optional minify.	False
minify	bool	Whether to minify the result of the intersection of the two DFAs.	True

Returns:

Type	Description
Self	A DFA accepting the intersection of the two input DFAs. State minimal by default.

isdisjoint(other)

Returns True if the language accepted by self is disjoint from that of other.

Parameters:

Name	Type	Description	Default
other	DFA	The other DFA we are comparing our language against.	required

Returns:

Type	Description
bool	True if self is disjoint from other, False otherwise.

isempty()

Returns True if the language accepted by self is empty.

Returns:

Type	Description
bool	True if self accepts the empty language, False otherwise.

isfinite()

Returns True if the language accepted by self is finite.

Returns:

Type	Description
bool	True if self accepts a finite language, False otherwise.

issubset(other)

Returns True if the language accepted by self is a subset of that of other.

Parameters:

Name	Type	Description	Default
other	DFA	The other DFA we are comparing our language against.	required

Returns:

Type	Description
bool	True if self is a subset of other, False otherwise.

issuperset(other)

Returns True if the language accepted by self is a superset of that of other.

Parameters:

Name	Type	Description	Default
other	DFA	The other DFA we are comparing our language against.	required

Returns:

Type	Description
bool	True if self is a superset of other, False otherwise.

iter_transitions()

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

Returns:

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

maximum_word_length()

Returns the length of the longest word in the language accepted by the DFA In the case of infinite languages, None is returned.

Returns:

Type	Description
Optional[int]	The length of the longest word accepted by self. None if the language is infinite.

Raises:

Type	Description
EmptyLanguageException	Raised if self accepts the empty language.

minify(retain_names=False)

Create a minimal DFA which accepts the same inputs as this DFA.

First, non-reachable states are removed. Then, indistinguishable states are merged using Hopcroft's Algorithm.

Parameters:

Name	Type	Description	Default
retain_names	bool	Whether to retain original names when merging states. New names are from 0 to n-1.	False

Returns:

Type	Description
Self	A state-minimal equivalent DFA. May be complete in some cases if the input is partial.

minimum_word_length()

Returns the length of the shortest word in the language accepted by the DFA.

Returns:

Type	Description
int	The length of the shortest word accepted by self.

Raises:

Type	Description
EmptyLanguageException	Raised if self accepts an empty language.

nth_from_end(input_symbols, symbol, n) classmethod

Directly computes the minimal DFA which accepts all words whose nth character from the end is symbol, where n is a positive integer.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
symbol	str	The target input symbol.	required
n	int	The position of the target input symbol.	required

Returns:

Type	Description
Self	The DFA accepting the desired language.

nth_from_start(input_symbols, symbol, n) classmethod

Directly computes the minimal DFA which accepts all words whose nth character from the start is symbol, where n is a positive integer.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
symbol	str	The target input symbol.	required
n	int	The position of the target input symbol.	required

Returns:

Type	Description
Self	The DFA accepting the desired language.

of_length(input_symbols, *, min_length=0, max_length=None, symbols_to_count=None) classmethod

Directly computes the minimal DFA recognizing strings whose length is between min_length and max_length, inclusive. To allow arbitrarily long words, the value None can be passed in for max_length.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required
min_length	int	The minimum length of strings to be accepted by this DFA.	0
max_length	Optional[int]	The maximum length of strings to be accepted by this DFA. If set to None, there is no maximum.	None
symbols_to_count	Optional[AbstractSet[str]]	The input symbols to count towards the length of words to accepts. If set to None, counts all symbols.	None

Returns:

Type	Description
Self	The DFA accepting the desired language.

predecessor(input_str, *, strict=True, key=None)

Returns the first string accepted by the DFA that comes before the input string in lexicographical order.

Parameters:

Name	Type	Description	Default
input_str	str	The starting input string.	required
strict	bool	If set to false and input_str is accepted by the DFA, input_str will be returned.	True
key	Optional[Callable]	Function for defining custom lexicographical ordering. Defaults to using the standard string ordering.	None

Returns:

Type	Description
str	The first string accepted by the DFA lexicographically before input_string.

Raises:

Type	Description
InfiniteLanguageException	Raised if the language accepted by self is infinite, as we cannot generate predecessors in this case.

predecessors(input_str, *, strict=True, key=None)

Generates all strings that come before the input string in lexicographical order.

Parameters:

Name	Type	Description	Default
input_str	str	The starting input string.	required
strict	bool	If set to false and input_str is accepted by the DFA, input_str will be returned.	True
key	Optional[Callable]	Function for defining custom lexicographical ordering. Defaults to using the standard string ordering.	None

Returns:

Type	Description
Generator[str, None, None]	A generator for all strings that come before the input string in lexicographical order.

Raises:

Type	Description
InfiniteLanguageException	Raised if the language accepted by self is infinite, as we cannot generate predecessors in this case.

random_word(k, *, seed=None)

Returns a random word of length k accepted by self.

Parameters:

Name	Type	Description	Default
k	int	The length of the desired word.	required
seed	Optional[int]	The random seed to use for the sampling of the random word.	None

Returns:

Type	Description
str	A uniformly random word of length k accepted by the DFA self.

Raises:

Type	Description
ValueError	If this DFA does not accept any words of length k.

read_input_stepwise(input_str, ignore_rejection=False)

Return a generator that yields each step while reading input.

Parameters:

Name	Type	Description	Default
input_str	str	The input string to read.	required
ignore_rejection	bool	Whether to throw an exception if the input string is rejected.	False

Yields:

Type	Description
Generator[DFAStateT, None, None]	A generator that yields the current configuration of the DFA after each step of reading input.

Raises:

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

successor(input_str, *, strict=True, key=None)

Returns the first string accepted by the DFA that comes after the input string in lexicographical order.

Parameters:

Name	Type	Description	Default
input_str	Optional[str]	The starting input string. If None, will generate all words.	required
strict	bool	If set to false and input_str is accepted by the DFA, input_str will be returned.	True
key	Optional[Callable]	Function for defining custom lexicographical ordering. Defaults to using the standard string ordering.	None

Returns:

Type	Description
str	The first string accepted by the DFA lexicographically before input_string.

successors(input_str, *, strict=True, key=None, reverse=False)

Generates all strings that come after the input string in lexicographical order.

Parameters:

Name	Type	Description	Default
input_str	Optional[str]	The starting input string. If None, will generate all words.	required
strict	bool	If set to false and input_str is accepted by the DFA, input_str will be returned.	True
key	Optional[Callable]	Function for defining custom lexicographical ordering. Defaults to using the standard string ordering.	None
reverse	bool	If True, then predecessors will be generated instead of successors.	False

Returns:

Type	Description
Generator[str, None, None]	A generator for all strings that come after the input string in lexicographical order.

symmetric_difference(other, *, retain_names=False, minify=True)

Takes as input two DFAs M1 and M2 which accept languages L1 and L2 respectively. Returns a DFA which accepts the symmetric difference of L1 and L2.

Minifies by default. Unreachable states are always removed. If either input DFA is partial, the result is partial.

Parameters:

Name	Type	Description	Default
other	DFA	The DFA we want to take a symmetric difference with.	required
retain_names	bool	Whether to retain state names through the symmetric difference and optional minify.	False
minify	bool	Whether to minify the result of the symmetric difference of the two DFAs.	True

Returns:

Type	Description
Self	A DFA accepting the symmetric difference of the two input DFAs. State minimal by default.

to_complete(trap_state=None)

Creates an equivalent complete DFA with trap_state used as the name for an added trap state. If trap_state is not passed in, defaults to the largest negative integer which is not already a state name. If the DFA is already complete, just returns a copy.

Parameters:

Name	Type	Description	Default
trap_state	Optional[DFAStateT]	Name for custom trap state to be used.	None

Returns:

Type	Description
Self	An equivalent complete DFA.

to_partial(*, retain_names=False, minify=True)

Turns a DFA (complete or not) into a partial DFA. Removes dead states and trap states (except the initial state) and all edges leading to them.

Parameters:

Name	Type	Description	Default
minify	bool	Whether to perform a minify operation while converting to a partial DFA.	True
retain_names	bool	Whether to retain state names during minification.	True

Returns:

Type	Description
Self	An equivalent partial DFA.

union(other, *, retain_names=False, minify=True)

Takes as input two DFAs M1 and M2 which accept languages L1 and L2 respectively. Returns a DFA which accepts the union of L1 and L2.

Minifies by default. Unreachable states are always removed. If either input DFA is partial, the result is partial.

Parameters:

Name	Type	Description	Default
other	DFA	The DFA we want to take a union with.	required
retain_names	bool	Whether to retain state names through the union and optional minify.	False
minify	bool	Whether to minify the result of the union of the two DFAs.	True

Returns:

Type	Description
Self	A DFA accepting the union of the two input DFAs. State minimal by default.

universal_language(input_symbols) classmethod

Directly computes the minimal DFA accepting all strings.

Parameters:

Name	Type	Description	Default
input_symbols	AbstractSet[str]	The set of input symbols to construct the DFA over.	required

Returns:

Type	Description
Self	The DFA accepting the desired language.

validate()

Raises an exception if this automaton is not internally consistent.

Raises:

Type	Description
InvalidStateError	If this DFA has invalid states in the transition dictionary.
MissingStateError	If this DFA has states missing from the transition dictionary.
InvalidSymbolError	If this DFA has invalid symbols in the transition dictionary.
MissingSymbolError	If this DFA is missing transitions on certain symbols.

words_of_length(k)

Generates all words of length k in the language accepted by the DFA.

Parameters:

Name	Type	Description	Default
k	int	The desired word length.	required

Returns:

Type	Description
Generator[str, None, None]	A generator for all words of length k accepted by the DFA.