Tools for Formal Languages manipulation
What is FAdo?
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.
It currently includes most standard operations for the manipulation of regular languages. Regular languages can be represented by regular expressions (RE) or finite automata, among other formalisms. Finite automata may be deterministic (DFA) or non-deterministic (NFA). 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.
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 (some with C implementations): Moore, Hopcroft, and some incremental algorithms. Brzozowski minimization is available for NFAs. 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.
For more details on the models and the respective operations implemented see documentation page.
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.
It currently includes most standard operations for the manipulation of regular languages. Regular languages can be represented by regular expressions (RE) or finite automata, among other formalisms. Finite automata may be deterministic (DFA) or non-deterministic (NFA). 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.
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 (some with C implementations): Moore, Hopcroft, and some incremental algorithms. Brzozowski minimization is available for NFAs. 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.
For more details on the models and the respective operations implemented see documentation page.
