Skip to main content

Python library for manipulating probabilistic automata.

Project description

Probabilistic Automata

Build Status Docs codecov PyPI version License: MIT

Python library for manipulating Probabilistic Automata. This library builds upon the dfa package.

Table of Contents


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

$ pip install probabilistic_automata

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

$ poetry install


The probabilistic_automata library centers around the PDFA object which models a finite probabilistic transition system, e.g., a Markov Decision Process, as a DFA or Moore Machine over a product alphabet over the system's actions and the environment's stochastic action.

import probabilistic_automata as PA

def transition(state, composite_action):
    sys_action, env_action = composite_action
    return (state + sys_action + env_action) % 2

def env_dist(state, sys_action):
    """Based on state and the system action, what are the probabilities 
    of the environment's action."""

    return {0: 1/2, 1: 1/2}  # Always a coin flip.

noisy_parity = PA.pdfa(
    inputs={0, 1},
    env_inputs={0, 1},
    outputs={0, 1},
    env_dist=env_dist,   # Equivalently, PA.uniform({0, 1}).

The support and transition probabilities can easily calculated:

assert, 0) == {0, 1}
assert noisy_parity.transition_probs(0, 0) == {0: 1/2, 1: 1/2}
assert noisy_parity.prob(start=0, action=0, end=0) == 1/2

Dict <-> PDFA

Note that pdfa provides helper functions for going from a dictionary based representation of a probabilistic transition system to a PDFA object and back.

import probabilistic_automata as PA

mapping = {
    "s1": (True, {
        'a': {'s1': 0.5, 's2': 0.5},
    "s2": (False, {
        'a': {'s1': 1},

start = "s1"
pdfa = PA.dict2pdfa(mapping=mapping, start=start)
assert pdfa.inputs == {'a'}

mapping2, start2 = PA.pdfa2dict(pdfa)
assert start == start2
assert mapping2 == mapping


The probabilistic_automata library has two convenience methods for transforming a Deterministic Finite Automaton (dfa.DFA) into a PDFA.

  • The lift function simply creates a PDFA whose transitions are deterministic and match the original dfa.DFA.
import probabilistic_automata as PA
from dfa import DFA

parity = DFA(
    inputs={0, 1},
    transition=lambda s, c: (s + c) & 1,

parity_pdfa = lift(parity)

assert pdfa.inputs == parity.inputs
assert pdfa.env_inputs == {None}
  • The randomize function takes a DFA and returns a PDFA modeling the actions of the DFA being selected uniformly at random.
noisy_parity = PA.randomize(parity)

assert noisy_parity.inputs == {None}
assert noisy_parity.env_inputs == noisy_parity.inputs


Like their deterministic variants PDFA objects can be combined in two ways:

  1. (Synchronous) Cascading Composition: Feed outputs of one PDFA into another.
machine = noisy_parity >> noisy_parity

assert machine.inputs == noisy_parity.inputs
assert machine.outputs == noisy_parity.outputs
assert machine.start == (0, 0)

assert, 0), 0) == {(0, 0), (0, 1), (1, 0), (1, 1)}
  1. (Synchronous) Parallel Composition: Run two PDFAs in parallel.
machine = noisy_parity | noisy_parity

assert machine.inputs.left == noisy_parity.inputs
assert machine.inputs.right == noisy_parity.inputs

assert machine.outputs.left == noisy_parity.outputs
assert machine.outputs.right == noisy_parity.outputs

assert machine.env_inputs.left == noisy_parity.env_inputs
assert machine.env_inputs.right == noisy_parity.env_inputs

assert machine.start == (0, 0)
assert, 0), (0, 0)) == {(0, 0), (0, 1), (1, 0), (1, 1)}

Note Parallel composition results in a PDFA with dfa.ProductAlphabet input and output alphabets.

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

probabilistic_automata-0.4.2.tar.gz (10.3 kB view hashes)

Uploaded source

Built Distribution

Supported by

AWS AWS Cloud computing Datadog Datadog Monitoring Facebook / Instagram Facebook / Instagram PSF Sponsor Fastly Fastly CDN Google Google Object Storage and Download Analytics Huawei Huawei PSF Sponsor Microsoft Microsoft PSF Sponsor NVIDIA NVIDIA PSF Sponsor Pingdom Pingdom Monitoring Salesforce Salesforce PSF Sponsor Sentry Sentry Error logging StatusPage StatusPage Status page