skip to navigation
skip to content

FAdo 1.0.1

Formal Languages manipulation module

Package Documentation

Latest Version: 1.2

The FAdo system aims to provide an open source extensible high-performance software library for the symbolic manipulation of automata and other models of computation.

To allow high-level programming with complex data structures, easy prototyping of algorithms, and portability (to use in computer grid systems for example), are its main features. Our main motivation is the theoretical and experimental research, but we have also in mind the construction of a pedagogical tool for teaching automata theory and formal languages.

Regular Languages

It currently includes most standard operations for the manipulation of regular languages. Regular languages can be represented by regular expressions (regexp) or finite automata, among other formalisms. Finite automata may be deterministic (DFA), non-deterministic (NFA) or generalized (GFA). In FAdo these representations are implemented as Python classes.

Elementary regular languages operations as union, intersection, concatenation, complementation and reverse are implemented for each class. Also several combined operations are available for specific models.

Several conversions between these representations are implemented:

  • NFA -> DFA: subset construction
  • NFA -> RE: recursive method
  • GFA -> RE: state elimination, with possible choice of state orderings
  • RE -> NFA: Thompson method, Glushkov method, follow, Brzozowski, and partial derivatives.
  • For DFAs several minimization algorithms are available: Moore, Hopcroft, and some incremental algorithms. Brzozowski minimization is available for NFAs.
  • An algorithm for hyper-minimization of DFAs
  • Language equivalence of two DFAs can be determined by reducing their correspondent minimal DFA to a canonical form, or by the Hopcroft and Karp algorithm.
  • Enumeration of the first words of a language or all words of a given length (Cross Section)
  • Some support for the transition semigroups of DFAs

Finite Languages

Special methods for finite languages are available:

  • Construction of a ADFA (acyclic finite automata) from a set of words
  • Minimization of ADFAs
  • Several methods for ADFAs random generation
  • Methods for deterministic cover finite automata (DCFA)


Several methods for transducers in standard form (SFT) are available:

  • Rational operations: union, inverse, reversal, composition, concatenation, star
  • Test if a transducer is functional
  • Input intersection and Output intersection operations


A language property is a set of languages. Given a property specified by a transducer, several language tests are possible.

  • 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
  • Computation of the edit distance of a regular language, using input altering transducers



  • SFT.evalWordP() was returning the negation of what it should.

1.0 (Halifax)

  • addState() does not create states with clashing names (int/str) anymore.
  • New property builders having transducers as strings instead of stored in files.


  • yappy_parser permanent tables recover from reading problems, and quit shelf usage as last resort solution. Now it should work in all OS and in every possible conditions, even in a Apache execution environment
  • Intersection of properties corrected for input altering transducers
  • Normal Form Transducers
  • Conjunction of input properties described by input altering and input preserving transducers fixed
  • Infix Property added


  • Error corrected with the import of new yappy_parser
  • Now display() works in MSwindows, with ”start” instead of ”open”
File Type Py Version Uploaded on Size
FAdo-1.0.1-py2-none-any.whl (md5) Python Wheel 2.7 2014-06-08 139KB
FAdo-1.0.1.tar.gz (md5) Source 2014-06-08 123KB
  • Downloads (All Versions):
  • 17 downloads in the last day
  • 167 downloads in the last week
  • 934 downloads in the last month