Comp(ilation) of Aut(omata)

CompAut is Python module that aims to manipulate general finite states machines. Its global aim is research in the field of finite automata. It aims at simplicity and straightforward implementation and not towards performances.

Installation

For the whole system:

sudo python3 setup.py install

For the user only

sudo python3 setup.py --user install

It will install the lark-parser package as well.

Dependencies

• lark-parser For parsing stuff
• networkx: For algebraic computation
• matplotlib and pillow for image generations.

Usage

• The object cre (actually an instance of the class ClassicalRegularExpression) allows to transform regular expression (in a rather standard syntax) into automaton. It supports only a fraction of what Perl Regular expression allows.

Example:

Mail = cre.compile("[a-zA-Z]*@[a-z]*\.[a-z]{2,6}") # Build an automaton recognizing it.
assert "john@doe.com" in Mail
assert not "johnAdoe.com" in Mail

The object build that way is not meant to be efficient or to perform complicated operation.

• The class ̀Automaton allows to define classical automaton that can be executed into iterable and manipulate easily. An automaton is non mutable python object.

Its transitions are labeled by MetaLetter, essentially a finite or cofinite set of python object. To expression that a transition is taken by "a" and "b", we use allIn("ab").

To express that a transition is taken by everything except a and b, we use allExcept("ab").

ex:

A = Automaton.from_transitions([(0, allExcept("b"), 0), (0, allIn("a"), 1)], initial_states=[0], final_states=[0])
assert "ca" in A # We can check membership
assert ("c", "a") in A # It accepts arbitrary iterable
assert (3, "a") in A # actually allExcept will match any hashable that is not in it.
assert not "cba" in A
B = A.minimize() # Return a minimal version of the automaton.

• The submodules in machines contains many classes that implement in C language various variants of the automaton or expression we provides to them. A machine is morally a standalone program that can be executed outside Python. It is self documented and respect GNU-like toolchains.

• A machine is an executable but you can restore the abstract python object that generates it. The TemplateMachine class also contains basic operations to interact with the machine directly in Python.

• To add a new compilation procedure within the compilation chains, you can look at the submodule template.

Tutorials

The following tutorial are generated using jupyter notebook that can be found in the notebook folder of this repository.

• A short introduction
• Playing With algebra

Algebra

Basic algebraic automata theory are presents in the module, but still experimental.

Other model of computation

• Stack Automaton model are presents and can be manipulated but not yet statically compiled

Roadmap

• Introduce more static compilation procedure for finite automaton
• Improved algebraic tools and visualisation
• Introduce other target languages
• Add more logics
• XML and JSON machines.