Skip to main content
Join the official 2019 Python Developers SurveyStart the survey!

A Python package implementing automata.

Project description

Pythomata

Python implementation of automata theory.

Dependencies

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.

Install

Install from master branch:

  • with pip:

      pip3 install git+https://github.com/marcofavorito/pythomata.git
    
  • or, clone the repository and install:

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

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.

Tests

To run the tests:

tox

To run only the code style checks:

tox -e flake8

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-2019 Marco Favorito

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

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.2.0
Filename, size File type Python version Upload date Hashes
Filename, size pythomata-0.2.0.tar.gz (18.9 kB) File type Source Python version None Upload date Hashes View hashes

Supported by

Elastic Elastic Search Pingdom Pingdom Monitoring Google Google BigQuery Sentry Sentry Error logging AWS AWS Cloud computing DataDog DataDog Monitoring Fastly Fastly CDN SignalFx SignalFx Supporter DigiCert DigiCert EV certificate StatusPage StatusPage Status page