Python library for modeling DFAs, Moore Machines, and Transition Systems.

## Project description

# DFA

A simple python implementation of a DFA.

**Table of Contents**

**Features:**

- State can be any Hashable object.
- Alphabet can be any finite sequence of Hashable objects.
- Designed to be immutable and hashable (assuming components are immutable and hashable).
- Design choice to allow transition map and accepting set to be
given as functions rather than an explicit
`dict`

or`set`

.

# Installation

If you just need to use `dfa`

, you can just run:

`$ pip install dfa`

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

The `dfa`

api is centered around the `DFA`

object.

By default, the `DFA`

object models a `Deterministic Finite Acceptor`

,
e.g., a recognizer of a Regular Language.

**Example Usage:**

from dfa import DFA dfa1 = DFA( start=0, inputs={0, 1}, label=lambda s: (s % 4) == 3, transition=lambda s, c: (s + c) % 4, ) dfa2 = DFA( start="left", inputs={"move right", "move left"}, label=lambda s: s == "left", transition=lambda s, c: "left" if c == "move left" else "right", )

## Membership Queries

assert dfa1.label([1, 1, 1, 1]) assert not dfa1.label([1, 0]) assert dfa2.label(["move right"]*100 + ["move left"]) assert not dfa2.label(["move left", "move right"])

## Transitions and Traces

assert dfa1.transition([1, 1, 1]) == 3 assert list(dfa1.trace([1, 1, 1])) == [0, 1, 2, 3]

## Non-boolean output alphabets

Sometimes, it is useful to model an automata which can label a word
using a non-Boolean alphabet. For example, `{True, False, UNSURE}`

.

The `DFA`

object supports this by specifying the output alphabet.

UNSURE = None def my_labeler(s): if s % 4 == 2: return None return (s % 4) == 3 dfa3 = DFA( start=0, inputs={0, 1}, label=my_labeler, transition=lambda s, c: (s + c) % 4, outputs={True, False, UNSURE}, )

**Note:** If `outputs`

is set to `None`

, then no checks are done that
the outputs are within the output alphabet.

dfa3 = DFA( start=0, inputs={0, 1}, label=my_labeler, transition=lambda s, c: (s + c) % 4, outputs=None, )

## Moore Machines

Finally, by reinterpreting the structure of the `DFA`

object, one can
model a Moore Machine. For example, in 3 state counter, `dfa1`

, the
Moore Machine can output the current count.

assert dfa1.transduce(()) == () assert dfa1.transduce((1,)) == (False,) assert dfa1.transduce((1, 1, 1, 1)) == (False, False, False, True)

## Composition

`DFA`

objects can be combined in three ways:

- (Synchronous) Cascading Composition: Feed outputs of one
`DFA`

into another.

mod_5 = DFA( start=0, label=lambda s: s, transition=lambda s, c: (s + c) % 5, inputs={0, 1}, outputs={0, 1, 2, 3, 4}, ) eq_0 = DFA( start=0, label=lambda s: s == 0, transition=lambda s, c: c, inputs={0, 1, 2, 3, 4}, outputs={True, False} ) eq_0_mod_5 = eq_0 << mod_5 assert eq_0_mod_5.label([0, 0, 0, 0]) assert not eq_0_mod_5.label([0, 1, 0, 0, 0])

Note that we use Moore Machine semantics (as opposed to Mealy). Thus
`eq_0`

's input is determined by `mod_5`

's state *before* seeing the
input. Thus, the following holds.

assert not eq_0_mod_5.label([1, 1, 1, 1, 1]) assert eq_0_mod_5.label([1, 1, 1, 1, 1, 0])

- (Synchronous) Parallel Composition: Run two
`DFA`

s in parallel.

parity = DFA( start=0, inputs={0, 1}, label=lambda s: s, transition=lambda s, c: (s + c) & 1, ) self_composed = parity | parity assert self_composed.label([(0, 0), (1, 0)]) == (1, 0)

**Note** Parallel composition results in a `DFA`

with
`dfa.ProductAlphabet`

input and outputs.

- (Synchronous) Parallel Composition with shared inputs:

from dfa.utils import tee self_composed2 = parity | parity assert self_composed2.label([0, 1, 0]) == (1, 1)

## DFA <-> Dictionary

Note that `dfa`

provides helper functions for going from a dictionary
based representation of a deterministic transition system to a `DFA`

object and back.

from dfa import dfa2dict, dict2dfa # DFA encoded a nested dictionaries with the following # signature. # <state>: (<label>, {<action>: <next state>}) dfa_dict = { 0: (False, {0: 0, 1: 1}), 1: (False, {0: 1, 1: 2}), 2: (False, {0: 2, 1: 3}), 3: (True, {0: 3, 1: 0}) } # Dictionary -> DFA dfa = dict2dfa(dfa_dict, start=0) # DFA -> Dictionary dfa_dict2, start = dfa2dict(dfa) assert (dfa_dict, 0) == (dfa_dict2, start)

## Computing Reachable States

# Perform a depth first traversal to collect all reachable states. assert dfa1.states() == {0, 1, 2, 3}

## Sampling Paths

Often times, it is useful to sample a path between two states, say `a`

and `b`

. `dfa`

supports this using `dfa.utils.paths`

. This function
returns a generator of words, `w`

, such that `dfa.transition(w, start=b) == a`

. For example:

from dfa.utils import paths access_strings = paths( dfa1, start=0, end=1, # Optional. If not specified returns all paths # starting at `start`. max_length=7, # Defaults to float('inf') randomize=True, # Randomize the order. Shorter paths still found first. ) for word in access_strings: assert dfa1.transition(word, start=0) == 1

## Running interactively (Co-Routine API)

`dfa`

supports interactively stepping through a `DFA`

object via
co-routines. This is particularly useful when using DFA in a control
loop. For example, the following code counts how many `1`

's it takes
to advance `dfa1`

's state back to the start state.

machine = dfa1.run() start = next(machine) state = None count = 0 while state != start: count += 1 state = machine.send(1)

## Special Alphabets

Often times, explicitly representing an alphabet is tedious, impossible, or inefficient.

As such, `dfa`

currently provides the following alphabets (with more
planned in the future).

`dfa.ExplicitAlphabet`

: A wrapper around frozensets. Default type of`Alphabet`

.`dfa.SupAlphabet`

: Alphabet that contains all possible inputs (beware of [Russell's paradox}(https://en.wikipedia.org/wiki/Russell's_paradox)).`dfa.ProductAlphabet(left, right)`

: Alphabet representing the Cartesian product of`left`

and`right`

alphabets.`dfa.ExponentialAlphabet`

: Alphabet representing the product of a`base`

alphabet with itself`dim`

times.

## Visualizing DFAs

`dfa`

optionally supports visualizing DFAs using graphviz. To use this
functionality be sure to install `dfa`

using with the `draw`

option:

pip install dfa[draw]

or

poetry install -E draw

Then one can simply use `dfa.draw.write_dot`

to write a `.dot`

file
representing the DFA. This `.dot`

file can be rendered using any
graphviz supporting tool.

from dfa.draw import write_dot write_dot(dfa1, "path/to/dfa1.dot")

Using the `dot`

command in linux results in the following rendering of `dfa1`

.

`$ dot -Tsvg path/to/dfa1.dot > dfa1.svg`

## 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.

Filename, size | File type | Python version | Upload date | Hashes |
---|---|---|---|---|

Filename, size dfa-2.0.0-py3-none-any.whl (9.4 kB) | File type Wheel | Python version py3 | Upload date | Hashes View |

Filename, size dfa-2.0.0.tar.gz (12.3 kB) | File type Source | Python version None | Upload date | Hashes View |