Skip to main content

Python library for converting binary decision diagrams to automata.

Project description

bdd2dfa

Build Status codecov PyPI version License: MIT

A simple python wrapper around Binary Decision Diagrams (BDDs) to interpret them as Deterministic Finite Automata (DFAs).

The package takes as input a BDD from the dd package and returns a DFA from the dfa package.

Formally, the resulting DFA objects are quasi-reduced BDDs (QDDs) where the label of non-leaf states in the original BDD is None and all leaves self loop.

Table of Contents

Installation

If you just need to use bdd2dfa, you can just run:

$ pip install bdd2dfa

For developers, note that this project uses the poetry python package/dependency management tool. Please familarize yourself with it and then run:

$ poetry install

Usage

# Create BDD

from dd import BDD

manager.declare('x', 'y', 'z')
x, y, z = map(manager.var, 'xyz')
bexpr = x & y & z


# Convert to DFA

from bdd2dfa import to_dfa

dfa = to_dfa(bexpr)

assert len(dfa.states()) == 7

assert dfa.label([1, 1, 1, 1])      # BDD rejects.
assert not dfa.label([0, 1, 1, 1])  # BDD accepts.
assert dfa.label([1, 1]) is None    # Non-leaf node.

Project details


Download files

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

Source Distribution

bdd2dfa-0.2.0.tar.gz (3.7 kB view hashes)

Uploaded source

Built Distribution

bdd2dfa-0.2.0-py3-none-any.whl (3.7 kB view hashes)

Uploaded py3

Supported by

AWS AWS Cloud computing and Security Sponsor Datadog Datadog Monitoring Fastly Fastly CDN Google Google Download Analytics Microsoft Microsoft PSF Sponsor Pingdom Pingdom Monitoring Sentry Sentry Error logging StatusPage StatusPage Status page