Automata are abstract machines used to represent models of computation, and are a central object of study in theoretical computer science. Given an input string of characters over a fixed alphabet, these machines either accept or reject the string. A language corresponding to an automaton is the set of all strings it accepts. Three important families of automata in increasing order of generality are the following:
 Finitestate automata
 Pushdown automata
 Turing machines
The automata
package facilitates working with these families by allowing simulation of reading input and higherlevel manipulation
of the corresponding languages using specialized algorithms. For an overview on automata theory, see this Wikipedia article, and
for a more comprehensive introduction to each of these topics, see these lecture notes.
Statement of need
Automata are a core component of both computer science education and research, seeing further theoretical work
and applications in a wide variety of areas such as computational biology and networking.
Consequently, the manipulation of automata with software packages has seen significant attention from
researchers in the past. The similarly named Mathematica package Automata
implements a number of
algorithms for use with finitestate automata, including regular expression conversion and binary set operations.
In Java, the Brics package implements similar algorithms, while the JFLAP package places an emphasis
on interactivity and simulation of more general families of automata.
automata
serves the demand for such a package in the Python software ecosystem, implementing algorithms and allowing for
simulation of automata in a manner comparable to the packages described previously. As a popular highlevel language, Python enables
significant flexibility and ease of use that directly benefits many users. The package includes a comprehensive test suite,
support for modern language features (including type annotations), and has a large number of different automata,
meeting the demands of users across a wide variety of use cases. In particular, the target audience
is both researchers that wish to manipulate automata, and for those in educational contexts to reinforce understanding about how these
models of computation function.
Package features
The API of the package is designed to mimic the formal mathematical description of each automaton using builtin Python data structures
(such as sets and dicts). This is for ease of use by those that are unfamiliar with these models of computation, while also providing performance
suitable for tasks arising in research. In particular, algorithms in the package have been written for tackling
performance on large inputs, incorporating optimizations such as only exploring the reachable set of states
in the construction of a new finitestate automaton. The package also has native display integration with Jupyter
notebooks, enabling easy visualization that allows students to interact with automata
in an exploratory manner.
Of note are some commonly used and technical algorithms implemented in the package for finitestate automata:

An optimized version of the HopcroftKarp algorithm to determine whether two deterministic finite automata (DFA) are equivalent.

The product construction algorithm for binary set operations (union, intersection, etc.) on the languages corresponding to two input DFAs.

Thompson’s algorithm for converting regular expressions to equivalent nondeterministic finite automata (NFA).

Hopcroft’s algorithm for DFA minimization.

A specialized algorithm for directly constructing a stateminimal DFA accepting a given finite language.

A specialized algorithm for directly constructing a minimal DFA recognizing strings containing a given substring.
To the authors’ knowledge, this is the only Python package implementing all of the automata manipulation algorithms stated above.
Example usage
The following example is inspired by the use case described in this blog post. We wish to determine which strings in a given set are within the target edit distance to a reference string. We will first initialize a DFA corresponding to a fixed set of target words over the alphabet of all lowercase ascii characters.
from automata.fa.dfa import DFA
from automata.fa.nfa import NFA
import string
target_words_dfa = DFA.from_finite_language(
input_symbols=set(string.ascii_lowercase),
language={'these', 'are', 'target', 'words', 'them', 'those'},
)
Next, we construct an NFA recognizing all strings within a target edit distance of a fixed reference string, and then immediately convert this to an equivalent DFA. The package provides builtin functions to make this construction easy, and we use the same alphabet as the DFA that was just created.
words_within_edit_distance_dfa = DFA.from_nfa(
NFA.edit_distance(
input_symbols=set(string.ascii_lowercase),
reference_str='they',
max_edit_distance=2,
)
)
Finally, we take the intersection of the two DFAs we have constructed and read all of the words in the output DFA into a list. The library makes this straightforward and idiomatic.
found_words_dfa = target_words_dfa & words_within_edit_distance_dfa
found_words = list(found_words_dfa)
The DFA found_words_dfa
accepts strings in the intersection of the languages of the
DFAs given as input, and found_words
is a list containing this language. Note the power of this
technique is that the DFA words_within_edit_distance_dfa
has an infinite language, meaning we could not do this same computation just using the builtin
sets in Python directly (as they always represent a finite collection), although the
syntax used by automata
is very similar to promote intuition.
Citing
This post is adapted from our JOSS paper, which should be used for citations.
Leave a comment