Python library for modeling DFAs.
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
orset
.
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)
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}
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.