| Name | dfa JSON |
| Version |
4.7.1
JSON |
| download |
| home_page | https://github.com/mvcisback/dfa |
| Summary | Python library for modeling DFAs, Moore Machines, and Transition Systems. |
| upload_time | 2024-05-10 02:18:26 |
| maintainer | None |
| docs_url | None |
| author | Marcell Vazquez-Chanlatte |
| requires_python | <4.0,>=3.9 |
| license | MIT |
| keywords |
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# DFA
A simple python implementation of a DFA.
[](https://cloud.drone.io/mvcisback/dfa)
[](https://badge.fury.io/py/dfa)
[](https://opensource.org/licenses/MIT)
<!-- markdown-toc start - Don't edit this section. Run M-x markdown-toc-generate-toc again -->
**Table of Contents**
- [Installation](#installation)
- [Usage](#usage)
- [Membership Queries](#membership-queries)
- [Transitions and Traces](#transitions-and-traces)
- [Non-boolean output alphabets](#non-boolean-output-alphabets)
- [Moore Machines](#moore-machines)
- [DFA <-> Dictionary](#dfa---dictionary)
- [Computing Reachable States](#computing-reachable-states)
- [Sampling Paths](#sampling-paths)
- [Running interactively (Co-Routine API)](#running-interactively-co-routine-api)
- [Visualizing DFAs](#visualizing-dfas)
<!-- markdown-toc end -->
**Features:**
1. State can be any Hashable object.
2. Alphabet can be any finite sequence of Hashable objects.
3. Designed to be immutable and hashable (assuming components are
immutable and hashable).
4. 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](https://poetry.eustace.io/) 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:**
```python
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
```python
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
```python
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.
```python
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.
```python
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.
```python
assert dfa1.transduce(()) == ()
assert dfa1.transduce((1,)) == (False,)
assert dfa1.transduce((1, 1, 1, 1)) == (False, False, False, True)
```
## Language Queries
Utility functions are available for testing if a language:
1. Is empty: `utils.find_word`
2. Is equivilent to another language: `utils.find_equiv_counterexample`
3. Is a subset of a another language: `utils.find_subset_counterexample`
These operate by returning `None` if the property holds, i.e.,
`lang(dfa1) = ∅, lang(dfa1) ≡ lang(dfa2), lang(dfa1) ⊆ lang(dfa2)`, and
returning a counterexample `Word` otherwise.
## 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.
```python
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
```python
# Perform a depth first traversal to collect all reachable states.
assert dfa1.states() == {0, 1, 2, 3}
```
## Finding Words and Access strings
To generate accepting strings (words) in a DFA (breadth first using string length) one can use the `dfa.utils.words` function:
```python
from dfa.utils.import dfa2dict, words, find_words
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})
}
lang = dict2dfa(dfa_dict, start=0)
xs = set(fn.take(5, words(lang)))
assert len(xs) == 5
assert all(lang.label(x) for x in xs)
```
To get a single word, a helper function is provided in `dfa.utils.find_word` which returns `None` if the language of the DFA is empty:
```python
# ... Same as above ...
x = find_word(lang)
assert x is not None
assert lang.label(x)
```
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:
```python
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
```
## DFA minimization
DFAs can be minimized using the `minimize` method.
```python
my_dfa = my_dfa.minimize()
```
## DFA advancement (progression)
One can create the DFA starting at the state indexed by a given word by using
the `advance` method.
```python
my_dfa = my_dfa.advance(word)
```
## 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.
```python
machine = dfa1.run()
next(machine)
state = None
count = 0
while state != dfa1.start:
count += 1
state = machine.send(1)
```
## Visualizing DFAs
`dfa` optionally supports visualizing DFAs using graphviz. To use this
functionality be sure to install `dfa` using with the `draw` option:
```python
pip install dfa[draw]
```
or
```python
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.
```python
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`
<figure>
<img src="assets/dfa1.svg" alt="visualization of dfa1" width=500px>
<figcaption>
Visualization of dfa1 using graphviz.
</figcaption>
</figure>
Raw data
{
"_id": null,
"home_page": "https://github.com/mvcisback/dfa",
"name": "dfa",
"maintainer": null,
"docs_url": null,
"requires_python": "<4.0,>=3.9",
"maintainer_email": null,
"keywords": null,
"author": "Marcell Vazquez-Chanlatte",
"author_email": "marcell.vc@eecs.berkeley.edu",
"download_url": "https://files.pythonhosted.org/packages/91/f1/10fc7dab8e3f97ecf5dec345f61e13d74c2289587cd8da8efb460048727a/dfa-4.7.1.tar.gz",
"platform": null,
"description": "# DFA\n\nA simple python implementation of a DFA. \n\n[](https://cloud.drone.io/mvcisback/dfa)\n[](https://badge.fury.io/py/dfa)\n[](https://opensource.org/licenses/MIT)\n\n<!-- markdown-toc start - Don't edit this section. Run M-x markdown-toc-generate-toc again -->\n**Table of Contents**\n\n- [Installation](#installation)\n- [Usage](#usage)\n - [Membership Queries](#membership-queries)\n - [Transitions and Traces](#transitions-and-traces)\n - [Non-boolean output alphabets](#non-boolean-output-alphabets)\n - [Moore Machines](#moore-machines)\n - [DFA <-> Dictionary](#dfa---dictionary)\n - [Computing Reachable States](#computing-reachable-states)\n - [Sampling Paths](#sampling-paths)\n - [Running interactively (Co-Routine API)](#running-interactively-co-routine-api)\n - [Visualizing DFAs](#visualizing-dfas)\n\n<!-- markdown-toc end -->\n\n\n**Features:**\n\n1. State can be any Hashable object.\n2. Alphabet can be any finite sequence of Hashable objects.\n3. Designed to be immutable and hashable (assuming components are\n immutable and hashable).\n4. Design choice to allow transition map and accepting set to be\n given as functions rather than an explicit `dict` or `set`.\n\n# Installation\n\nIf you just need to use `dfa`, you can just run:\n\n`$ pip install dfa`\n\nFor developers, note that this project uses the\n[poetry](https://poetry.eustace.io/) python package/dependency\nmanagement tool. Please familarize yourself with it and then\nrun:\n\n`$ poetry install`\n\n# Usage\n\nThe `dfa` api is centered around the `DFA` object. \n\nBy default, the `DFA` object models a `Deterministic Finite Acceptor`,\ne.g., a recognizer of a Regular Language. \n\n**Example Usage:**\n```python\nfrom dfa import DFA\n\ndfa1 = DFA(\n start=0,\n inputs={0, 1},\n label=lambda s: (s % 4) == 3,\n transition=lambda s, c: (s + c) % 4,\n)\n\ndfa2 = DFA(\n start=\"left\",\n inputs={\"move right\", \"move left\"},\n label=lambda s: s == \"left\",\n transition=lambda s, c: \"left\" if c == \"move left\" else \"right\",\n)\n```\n\n## Membership Queries\n\n```python\nassert dfa1.label([1, 1, 1, 1])\nassert not dfa1.label([1, 0])\n\nassert dfa2.label([\"move right\"]*100 + [\"move left\"])\nassert not dfa2.label([\"move left\", \"move right\"])\n```\n\n## Transitions and Traces\n\n```python\nassert dfa1.transition([1, 1, 1]) == 3\nassert list(dfa1.trace([1, 1, 1])) == [0, 1, 2, 3]\n```\n\n## Non-boolean output alphabets\n\nSometimes, it is useful to model an automata which can label a word\nusing a non-Boolean alphabet. For example, `{True, False, UNSURE}`.\n\nThe `DFA` object supports this by specifying the output alphabet.\n\n```python\nUNSURE = None\n\ndef my_labeler(s):\n if s % 4 == 2:\n return None\n return (s % 4) == 3\n\n\ndfa3 = DFA(\n start=0,\n inputs={0, 1},\n label=my_labeler,\n transition=lambda s, c: (s + c) % 4,\n outputs={True, False, UNSURE},\n)\n```\n\n**Note:** If `outputs` is set to `None`, then no checks are done that\nthe outputs are within the output alphabet.\n\n```python\ndfa3 = DFA(\n start=0,\n inputs={0, 1},\n label=my_labeler,\n transition=lambda s, c: (s + c) % 4,\n outputs=None,\n)\n```\n\n## Moore Machines\n\nFinally, by reinterpreting the structure of the `DFA` object, one can\nmodel a Moore Machine. For example, in 3 state counter, `dfa1`, the\nMoore Machine can output the current count.\n\n```python\nassert dfa1.transduce(()) == ()\nassert dfa1.transduce((1,)) == (False,)\nassert dfa1.transduce((1, 1, 1, 1)) == (False, False, False, True)\n```\n\n## Language Queries\n\nUtility functions are available for testing if a language:\n\n1. Is empty: `utils.find_word`\n2. Is equivilent to another language: `utils.find_equiv_counterexample`\n3. Is a subset of a another language: `utils.find_subset_counterexample`\n\nThese operate by returning `None` if the property holds, i.e.,\n`lang(dfa1) = \u2205, lang(dfa1) \u2261 lang(dfa2), lang(dfa1) \u2286 lang(dfa2)`, and\nreturning a counterexample `Word` otherwise.\n\n## DFA <-> Dictionary\n\nNote that `dfa` provides helper functions for going from a dictionary\nbased representation of a deterministic transition system to a `DFA`\nobject and back.\n\n```python\nfrom dfa import dfa2dict, dict2dfa\n\n# DFA encoded a nested dictionaries with the following\n# signature.\n# <state>: (<label>, {<action>: <next state>})\n\ndfa_dict = {\n 0: (False, {0: 0, 1: 1}),\n 1: (False, {0: 1, 1: 2}),\n 2: (False, {0: 2, 1: 3}), \n 3: (True, {0: 3, 1: 0})\n}\n\n# Dictionary -> DFA\ndfa = dict2dfa(dfa_dict, start=0)\n\n# DFA -> Dictionary\ndfa_dict2, start = dfa2dict(dfa)\n\nassert (dfa_dict, 0) == (dfa_dict2, start)\n```\n\n## Computing Reachable States\n\n```python\n# Perform a depth first traversal to collect all reachable states.\nassert dfa1.states() == {0, 1, 2, 3}\n```\n\n## Finding Words and Access strings\n\nTo generate accepting strings (words) in a DFA (breadth first using string length) one can use the `dfa.utils.words` function:\n\n```python\nfrom dfa.utils.import dfa2dict, words, find_words\n\ndfa_dict = {\n 0: (False, {0: 0, 1: 1}),\n 1: (False, {0: 1, 1: 2}),\n 2: (False, {0: 2, 1: 3}),\n 3: (True, {0: 3, 1: 0})\n}\nlang = dict2dfa(dfa_dict, start=0)\n\nxs = set(fn.take(5, words(lang)))\nassert len(xs) == 5\nassert all(lang.label(x) for x in xs)\n```\n\nTo get a single word, a helper function is provided in `dfa.utils.find_word` which returns `None` if the language of the DFA is empty:\n\n```python\n# ... Same as above ...\n\nx = find_word(lang)\nassert x is not None\nassert lang.label(x)\n```\n\n\nOften times, it is useful to sample a path between two states, say `a`\nand `b`. `dfa` supports this using `dfa.utils.paths`. This function\nreturns a generator of words, `w`, such that `dfa.transition(w,\nstart=b) == a`. For example:\n\n\n```python\nfrom dfa.utils import paths\n\naccess_strings = paths(\n dfa1, \n start=0,\n end=1, # Optional. If not specified returns all paths\n # starting at `start`.\n max_length=7, # Defaults to float('inf')\n randomize=True, # Randomize the order. Shorter paths still found first.\n)\n\nfor word in access_strings:\n assert dfa1.transition(word, start=0) == 1\n```\n\n## DFA minimization\n\nDFAs can be minimized using the `minimize` method.\n\n```python\nmy_dfa = my_dfa.minimize()\n```\n\n## DFA advancement (progression)\n\nOne can create the DFA starting at the state indexed by a given word by using\nthe `advance` method. \n\n```python\nmy_dfa = my_dfa.advance(word)\n```\n\n\n## Running interactively (Co-Routine API)\n\n`dfa` supports interactively stepping through a `DFA` object via\nco-routines. This is particularly useful when using DFA in a control\nloop. For example, the following code counts how many `1`'s it takes\nto advance `dfa1`'s state back to the start state.\n\n```python\n\nmachine = dfa1.run()\n\nnext(machine)\nstate = None\n\ncount = 0\nwhile state != dfa1.start:\n count += 1\n state = machine.send(1)\n```\n\n## Visualizing DFAs\n\n`dfa` optionally supports visualizing DFAs using graphviz. To use this\nfunctionality be sure to install `dfa` using with the `draw` option:\n\n```python\npip install dfa[draw]\n```\n\nor \n\n```python\npoetry install -E draw\n```\n\nThen one can simply use `dfa.draw.write_dot` to write a `.dot` file\nrepresenting the DFA. This `.dot` file can be rendered using any\ngraphviz supporting tool.\n\n```python\nfrom dfa.draw import write_dot\n\nwrite_dot(dfa1, \"path/to/dfa1.dot\")\n```\n\nUsing the `dot` command in linux results in the following rendering of `dfa1`.\n\n`$ dot -Tsvg path/to/dfa1.dot > dfa1.svg`\n\n<figure>\n <img src=\"assets/dfa1.svg\" alt=\"visualization of dfa1\" width=500px>\n <figcaption>\n Visualization of dfa1 using graphviz.\n </figcaption>\n</figure>\n",
"bugtrack_url": null,
"license": "MIT",
"summary": "Python library for modeling DFAs, Moore Machines, and Transition Systems.",
"version": "4.7.1",
"project_urls": {
"Homepage": "https://github.com/mvcisback/dfa",
"Repository": "https://github.com/mvcisback/dfa"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "582850282eb0a5fe324cdb81977817dc5c5d2ed167f9bb14f2f3cd80bebb0851",
"md5": "1fd6fc40ab1583b1eed79ad8a5ac68ec",
"sha256": "74950e54a477040d94ad06ae35cb9644a1fdceed99d65843923fb649d6a1784a"
},
"downloads": -1,
"filename": "dfa-4.7.1-py3-none-any.whl",
"has_sig": false,
"md5_digest": "1fd6fc40ab1583b1eed79ad8a5ac68ec",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": "<4.0,>=3.9",
"size": 11311,
"upload_time": "2024-05-10T02:18:25",
"upload_time_iso_8601": "2024-05-10T02:18:25.460256Z",
"url": "https://files.pythonhosted.org/packages/58/28/50282eb0a5fe324cdb81977817dc5c5d2ed167f9bb14f2f3cd80bebb0851/dfa-4.7.1-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "91f110fc7dab8e3f97ecf5dec345f61e13d74c2289587cd8da8efb460048727a",
"md5": "a8c420efde46b6c1020a7bcf5b5dacb1",
"sha256": "6ed1b33bad4adb6e4cc646dcde61fb2c8c7caeef15e69b978b48369db34f96e2"
},
"downloads": -1,
"filename": "dfa-4.7.1.tar.gz",
"has_sig": false,
"md5_digest": "a8c420efde46b6c1020a7bcf5b5dacb1",
"packagetype": "sdist",
"python_version": "source",
"requires_python": "<4.0,>=3.9",
"size": 13031,
"upload_time": "2024-05-10T02:18:26",
"upload_time_iso_8601": "2024-05-10T02:18:26.944924Z",
"url": "https://files.pythonhosted.org/packages/91/f1/10fc7dab8e3f97ecf5dec345f61e13d74c2289587cd8da8efb460048727a/dfa-4.7.1.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-05-10 02:18:26",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "mvcisback",
"github_project": "dfa",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "dfa"
}
