The FAdo system aims to provide an open source extensible software
library for the symbolic manipulation of regular languages and other
formal languages. FAdo is implemented in Python and currently
includes most standard operations for the manipulation of regular
languages through finite automata (Python classes DFA, NFA, or
GFA) and regular expressions (reex). Elementary regular language
operations, such as, union, intersection, complementation,
concatenation, iteration, and reverse are implemented for each
class. Many combined operations have specialized
algorithms. Witness families for several operational complexity lower
bounds are defined and canonical representations are supported.
Several conversions between representations are implemented: NFA to
DFA, NFA to reex, GFA to reex, reex to NFA, etc.. For DFA, several
minimization (and hyperminimazation) algorithms are available: Moore,
Hopcroft, Brzozowski, and some incremental algorithms. NFA
minimization via universal automata is implemented but with the
inherent inefficiency. Extended regular expressions modulo some algebraic properties are also supported. Some support is provided for computing
syntactic semigroups. There are several algorithms for language
equivalence based on bisimulation-like algorithms. Finite languages
can also be represented, by tries, AFA (acyclic finite
automata) and cover automata. Exact and random generators for some classes of automata
and regular expressions are also available.
Several methods for transducers in standard form (SFT) are implemented, such as rational operations (union, inverse, reversal, composition, concatenation, star); product operations (input and output intersection); test and witness of non functionality. A language property is a set of languages. Given a property specified by a transducer, several language tests are possible with application in code theory:
satisfaction i.e. if a language satisfies the property;maximality i.e. the language satisfies the property and is maximal;
properties implemented by transducers include: input preserving, input altering, trajectories, and fixed properties.
GUItar is a graphical user interface for
automata drawing and manipulation.
Its functionalities include visualization
and interactive editing, i.e. automatic and assisted diagram drawing;
and export/import filters
that allow the interaction with several symbolic manipulators.