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
|
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_substrings(input_symbols, substrings, *, contains=True, must_be_suffix=False)
classmethod
¶
Directly computes a DFA recognizing strings containing at least one of the
given substrings. The implementation is based on the Aho-Corasick
string-searching algorithm. If contains is set to False, then the
complement is constructed instead. If must_be_suffix is set to True,
then the each 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 |
substrings |
str
|
The set of strings to be recognized by this DFA. |
required |
contains |
bool
|
Whether or to construct the compliment DFA. |
True
|
must_be_suffix |
bool
|
Whether or not the target substrings 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, min_length=0, max_length=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
|
min_length |
int
|
Limits generation to words with at least the given length. |
0
|
max_length |
Optional[int]
|
Limits generation to words with at most the given length. |
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, min_length=0, max_length=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
|
min_length |
int
|
Limits generation to words with at least the given length. |
0
|
max_length |
Optional[int]
|
Limits generation to words with at most the given length. |
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, min_length=0, max_length=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
|
min_length |
int
|
Limits generation to words with at least the given length. |
0
|
max_length |
Optional[int]
|
Limits generation to words with at most the given length. |
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, min_length=0, max_length=None)
¶
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
|
min_length |
int
|
Limits generation to words with at least the given length. |
0
|
max_length |
Optional[int]
|
Limits generation to words with at most the given length. |
None
|
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. |