Pythomata

Python implementation of automata theory.

Links

• GitHub: https://github.com/whitemech/pythomata
• PyPI: https://pypi.org/project/pythomata/
• Documentation: https://whitemech.github.io/pythomata
• Changelog: https://whitemech.github.io/pythomata/release-history/
• Issue Tracker:https://github.com/whitemech/pythomata/issues
• Download: https://pypi.org/project/pythomata/#files

Install

• from PyPI:

pip install pythomata

• or, from source (e.g. develop branch):

pip install git+https://github.com/whitemech/pythomata.git@develop

• or, clone the repository and install:

git clone htts://github.com/whitemech/pythomata.git
cd pythomata
pip install .

How to use

• Define an automaton:

from pythomata import SimpleDFA
alphabet = {"a", "b", "c"}
states = {"s1", "s2", "s3"}
initial_state = "s1"
accepting_states = {"s3"}
transition_function = {
    "s1": {
        "b" : "s1",
        "a" : "s2"
    },
    "s2": {
        "a" : "s3",
        "b" : "s1"
    },
    "s3":{
        "c" : "s3"
    }
}
dfa = SimpleDFA(states, alphabet, initial_state, accepting_states, transition_function)

• Test word acceptance:

# a word is a list of symbols
word = "bbbac"
dfa.accepts(word)        # True

# without the last symbol c, the final state is not reached
dfa.accepts(word[:-1])   # False

• Operations such as minimization and trimming:

dfa_minimized = dfa.minimize()
dfa_trimmed = dfa.trim()

• Translate into a graphviz.Digraph instance:

graph = dfa.minimize().trim().to_graphviz()

To print the automaton:

graph.render("path_to_file")

For that you will need to install Graphviz. Please look at their download page for detailed instructions depending on your system.

The output looks like the following:

Features

• Basic DFA and NFA support;
• Algorithms for DFA minimization and trimming;
• Algorithm for NFA determinization;
• Translate automata into Graphviz objects.
• Support for Symbolic Automata.

Tests

To run the tests:

tox

To run only the code style checks:

tox -e flake8 -e mypy

Docs

To build the docs:

mkdocs build

To view documentation in a browser

mkdocs serve

and then go to http://localhost:8000

License

Pythomata is released under the GNU Lesser General Public License v3.0 or later (LGPLv3+).

Copyright 2018-2020 WhiteMech

Release History

0.3.2 (2020-03-22)

• Bug fixing and minor improvements.

0.3.1 (2020-02-28)

• Improved CI: using GitHub actions instead of Travis.
• Included many other checks: safety, black, liccheck.
• Improved documentation.

0.3.0 (2020-02-09)

• Main refactoring of the APIs.
• Introduce interfaces for better abstractions: Alphabet, FiniteAutomaton etc.
• DFA and NFA renamed SimpleDFA and SimpleNFA, respectively.
• Introduced SymbolicAutomaton and SymbolicDFA, where the guards on transitions are propositoinal formulas.

0.2.0 (2019-09-30)

• Refactoring of the repository

0.1.0 (2019-04-13)

• Basic support for DFAs and NFAs.
• Algorithms for DFA minimization and trimming.
• Algorithm for NFA determinization.