pythomata 0.1.7rc0

A Python package implementing automata.

Pythomata

Python implementation of automata.

• Free software: MIT license

• Documentation: https://pythomata.readthedocs.io.

Install

Graphviz

For Debian systems, the following commands should work:

$ wget http://ftp.it.debian.org/debian/pool/main/g/graphviz/graphviz_2.38.0-17_amd64.deb
$ sudo dpkg -i graphviz_2.38.0-1~saucy_amd64.deb
$ sudo apt-get install -f

Otherwise check the installation guide from the official site

How to use

• Define an automaton:

from pythomata.dfa import DFA
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 = DFA(states, alphabet, initial_state, accepting_states, transition_function)

• Test word acceptance:

# a word is a list of symbols
word = [b, b, b, a, b, c]

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

• Print the automata:

filepath = "./my_awesome_automaton"
dfa.minimize().trim().to_dot(filepath)

The output in .svg format is the following:

Features

• Basic DFA and NFA support;

• Algorithms for DFA minimization and trimming;

• Algorithm for NFA determinization;

• Print automata in SVG format.

Credits

This package was created with Cookiecutter and the audreyr/cookiecutter-pypackage project template.

History

0.1.0 (2018-03-13)

• First release on PyPI.

0.1.1 (2018-03-15)

• Basic DFA and NFA support;

• Algorithms for DFA minimization and trimming;

• Algorithm for NFA determinization.

0.1.2 (2018-03-16)

• Minor bug fixes

0.1.3 (2018-03-16)

• Changes in word acceptance procedure for DFAs