A Python package for automata theory.
Project description
Pythomata
Python implementation of automata theory.
- Documentation: https://whitemech.github.io/pythomata.
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.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
andNFA
renamedSimpleDFA
andSimpleNFA
, respectively.- Introduced
SymbolicAutomaton
andSymbolicDFA
, where the guards on transitions are propositoinal formulas.
0.3.1 (2020-02-28)
- Improved CI: using GitHub actions instead of Travis.
- Included many other checks:
safety
,black
,liccheck
. - Improved documentation.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
pythomata-0.3.1.tar.gz
(39.1 kB
view hashes)
Built Distribution
Close
Hashes for pythomata-0.3.1-py2.py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1c8841de7907d05bfd672de766b4275738729a4c3e99c6474c649b45c4a2841b |
|
MD5 | 303d5bb7f1436eacd52c2a51232e0338 |
|
BLAKE2b-256 | 3b3c0bd324d0be33c9d35c8d6293f147d27730ce16a1dc8551b804ef7beae461 |