Skip to main content

A Python package for automata theory.

Project description

Pythomata

codecov

Python implementation of automata theory.

Links

Install

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()
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.

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Files for pythomata, version 0.3.2
Filename, size File type Python version Upload date Hashes
Filename, size pythomata-0.3.2-py2.py3-none-any.whl (23.6 kB) File type Wheel Python version py2.py3 Upload date Hashes View
Filename, size pythomata-0.3.2.tar.gz (55.5 kB) File type Source Python version None Upload date Hashes View

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring DigiCert DigiCert EV certificate Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page