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.

What is GUItar?

GUItar is a visualization software tool for various types of automata (standard, weighted, pushdown, transducers, Turing machines, etc.). Its purposes include automatic and assisted diagram drawing, algorithm animation, interactive editing and export/import filters.

It is (for now) implemented with the wxPython graphical toolkit and the canvas is based on Floatcanvas

Here is an overview of GUItar graphical interface:

GUItar is a visualization software tool for various types of automata (standard, weighted, pushdown, transducers, Turing machines, etc.). Its purposes include automatic and assisted diagram drawing, algorithm animation, interactive editing and export/import filters.

It is (for now) implemented with the wxPython graphical toolkit and the canvas is based on Floatcanvas

Here is an overview of GUItar graphical interface:

Main features are:

Near future expected developments:

- Interactive drawing of several types of graph diagrams
- Complex style managers for nodes and edges
- (Very) Simple layout algorithms
- Import and Export for GraphMl, Vaucanson-G, and dot.
- Generic Foreign Function Calls (FFC) interface, specialised for FAdo system

Near future expected developments:

- Automatic Drawing of automata diagrams
- Reorganisation of the classifier, semaphores and profiler
- Improved styles manipulations
- Proper management of the information related to a given diagram
- Improved interface to FAdo system (and generic FFCs) to allow a better access to related information
- Performance improvements, general improvements and bug fixes