Pythomata

Python implementation of automata theory.

• Free software: Apache 2.0
• Documentation: https://whitemech.github.io/pythomata.

Install

• from PyPI:

  pip install pythomata
  pip install pythomata=0.3.0a  # for the pre-release.
  

• or, from source (master branch):

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

• 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

Copyright 2018-2020 WhiteMech

History

0.1.0 (2019-04-13)

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

0.2.0 (2019-09-30)

• Refactoring of the repository

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.