Skip to main content

Visual Automata is a Python 3 library built as a wrapper for the Automata library to add more visualization features.

Project description

Visual Automata

Latest Version Supported Python versions Downloads Coverage

Copyright 2021 Lewi Lie Uberg
Released under the MIT license

Visual Automata is a Python 3 library built as a wrapper for the Automata library to add more visualization features.

Contents

Prerequisites

pip install automata-lib
pip install pandas
pip install graphviz
pip install colormath
pip install jupyterlab

Installing

pip install visual-automata

Finite Automaton (FA)

VisualDFA

Importing

Import needed classes.

from automata.fa.dfa import DFA

from visual_automata.fa.dfa import VisualDFA

Instantiating DFAs

Define an visual_automata DFA that can accept any string ending with 00 or 11.

dfa = VisualDFA(
    states={"q0", "q1", "q2", "q3", "q4"},
    input_symbols={"0", "1"},
    transitions={
        "q0": {"0": "q3", "1": "q1"},
        "q1": {"0": "q3", "1": "q2"},
        "q2": {"0": "q3", "1": "q2"},
        "q3": {"0": "q4", "1": "q1"},
        "q4": {"0": "q4", "1": "q1"},
    },
    initial_state="q0",
    final_states={"q2", "q4"},
)

Converting

An automata-lib DFA can be converted to a VisualDFA.

Define an automata-lib DFA that can accept any string ending with 00 or 11.

dfa = DFA(
    states={"q0", "q1", "q2", "q3", "q4"},
    input_symbols={"0", "1"},
    transitions={
        "q0": {"0": "q3", "1": "q1"},
        "q1": {"0": "q3", "1": "q2"},
        "q2": {"0": "q3", "1": "q2"},
        "q3": {"0": "q4", "1": "q1"},
        "q4": {"0": "q4", "1": "q1"},
    },
    initial_state="q0",
    final_states={"q2", "q4"},
)

Convert automata-lib DFA to VisualDFA.

dfa = VisualDFA(dfa)

Transition Table

Outputs the transition table for the given DFA.

dfa.table
       0    1
→q0   q3   q1
q1    q3  *q2
*q2   q3  *q2
q3   *q4   q1
*q4  *q4   q1

Minimal-DFA

Creates a minimal DFA which accepts the same inputs as the old one. Unreachable states are removed and equivalent states are merged. States are renamed by default.

new_dfa = VisualDFA(
    states={'q0', 'q1', 'q2'},
    input_symbols={'0', '1'},
    transitions={
        'q0': {'0': 'q0', '1': 'q1'},
        'q1': {'0': 'q0', '1': 'q2'},
        'q2': {'0': 'q2', '1': 'q1'}
    },
    initial_state='q0',
    final_states={'q1'}
)
new_dfa.table
      0    1
→q0  q0  *q1
*q1  q0   q2
q2   q2  *q1
new_dfa.show_diagram()

alt text

minimal_dfa = VisualDFA.minify(new_dfa)
minimal_dfa.show_diagram()

alt text

minimal_dfa.table
                0        1
→{q0,q2}  {q0,q2}      *q1
*q1       {q0,q2}  {q0,q2}

Check input strings

1001 does not end with 00 or 11, and is therefore Rejected

dfa.input_check("1001")
          [Rejected]                         
Step: Current state: Input symbol: New state:
1                →q0             1         q1
2                 q1             0         q3
3                 q3             0        *q4
4                *q4             1         q1

10011 does end with 11, and is therefore Accepted

dfa.input_check("10011")
          [Accepted]                         
Step: Current state: Input symbol: New state:
1                →q0             1         q1
2                 q1             0         q3
3                 q3             0        *q4
4                *q4             1         q1
5                 q1             1        *q2

Show Diagram

For IPython dfa.show_diagram() may be used.
For a python script dfa.show_diagram(view=True) may be used to automatically view the graph as a PDF file.

dfa.show_diagram()

alt text

The show_diagram method also accepts input strings, and will return a graph with gradient red arrows for Rejected results, and gradient green arrows for Accepted results. It will also display a table with transitions states stepwise. The steps in this table will correspond with the [number] over each traversed arrow.

Please note that for visual purposes additional arrows are added if a transition is traversed more than once.

dfa.show_diagram("1001")
          [Rejected]                         
Step: Current state: Input symbol: New state:
1                →q0             1         q1
2                 q1             0         q3
3                 q3             0        *q4
4                *q4             1         q1

alt text

dfa.show_diagram("10011")
          [Accepted]                         
Step: Current state: Input symbol: New state:
1                →q0             1         q1
2                 q1             0         q3
3                 q3             0        *q4
4                *q4             1         q1
5                 q1             1        *q2

alt text

VisualNFA

Importing

Import needed classes.

from automata.fa.nfa import NFA

from visual_automata.fa.nfa import VisualNFA

Instantiating NFAs

Define an visual_automata NFA that can accept any string with the pattern 10, 1010, 101010.

nfa = VisualNFA(
    states={"q0", "q1", "q2"},
    input_symbols={"0", "1"},
    transitions={
        "q0": {"": {"q2"}, "1": {"q1"}},
        "q1": {"1": {"q2"}, "0": {"q0", "q2"}},
        "q2": {},
    },
    initial_state="q0",
    final_states={"q0"},
)

Converting

An automata-lib NFA can be converted to a VisualNFA.

Define an automata-lib NFA that can accept any string with the pattern 10, 1010, 101010.

nfa = NFA(
    states={"q0", "q1", "q2"},
    input_symbols={"0", "1"},
    transitions={
        "q0": {"": {"q2"}, "1": {"q1"}},
        "q1": {"1": {"q2"}, "0": {"q0", "q2"}},
        "q2": {},
    },
    initial_state="q0",
    final_states={"q0"},
)

Convert automata-lib NFA to VisualNFA.

nfa = VisualNFA(nfa)

Transition Table

Outputs the transition table for the given DFA.

nfa.table
             0   1   λ
→*q0         ∅  q1  q2
q1    {*q0,q2}  q2   ∅
q2           ∅   ∅   ∅

Eliminate lambda/epsilon

Creates a NFA with lambda transitions removed.

nfa_eliminated = VisualNFA.eliminate_lambda(nfa)
nfa_eliminated.table
             0   1
→*q0         ∅  q1
q1    {*q0,q2}  q2
q2           ∅   ∅
nfa_eliminated.show_diagram()

alt text

Check input strings

101 does not correspond with the pattern 10, 1010, 101010, and is therefore Rejected

nfa.input_check("101")
          [Rejected]                         
Step: Current state: Input symbol: New state:
1               →*q0             1         q1
2                 q1             0         q2
3                 q2             1          ∅

1010 does correspond with the pattern 10, 1010, 101010, and is therefore Accepted

nfa.input_check("1010")
          [Accepted]                         
Step: Current state: Input symbol: New state:
1               →*q0             1         q1
2                 q1             0       →*q0
3               →*q0             1         q1
4                 q1             0       →*q0

Show Diagram

For IPython nfa.show_diagram() may be used.
For a python script nfa.show_diagram(view=True) may be used to automatically view the graph as a PDF file.

nfa.show_diagram()

alt text

The show_diagram method also accepts input strings, and will return a graph with gradient red arrows for Rejected results, and gradient green arrows for Accepted results. It will also display a table with transitions states stepwise. The steps in this table will correspond with the [number] over each traversed arrow.

Please note that for visual purposes additional arrows are added if a transition is traversed more than once.

nfa.show_diagram("101")
          [Rejected]                         
Step: Current state: Input symbol: New state:
1               →*q0             1         q1
2                 q1             0         q2
3                 q2             1          ∅

alt text

nfa.show_diagram("1010")
          [Accepted]                         
Step: Current state: Input symbol: New state:
1               →*q0             1         q1
2                 q1             0       →*q0
3               →*q0             1         q1
4                 q1             0       →*q0

alt text

Please note that for long input strings, the path calculations may take some time.

big_nfa = VisualNFA(
    states={"q1", "q2", "q3", "q4", "q5", "q6", "q7", "q8"},
    input_symbols={"A", "C", "G", "T"},
    transitions={
        "q1": {"A": {"q7"}, "C": {"q4"}, "G": {"q4", "q2"}, "T": {"q4"}},
        "q2": {"A": {"q3", "q6"}, "C": {"q2", "q4"}, "G": {"q3", "q6"}, "T": {"q6"}},
        "q3": {"A": {"q8"}, "C": {"q8"}, "T": {"q8"}},
        "q4": {"A": {"q5"}, "C": {"q4"}, "G": {"q5"}, "T": {"q2", "q4", "q5"}},
        "q5": {"A": {"q3", "q8"}, "C": {"q3", "q8"}, "G": {"q8"}, "T": {"q3", "q8"}},
        "q6": {"A": {"q8"}, "C": {"q8"}, "G": {"q8"}, "T": {"q8"}},
        "q7": {"A": {"q7", "q8"}, "C": {"q7", "q8"}, "G": {"q8"}, "T": {"q3", "q8"}},
        "q8": {},
    },
    initial_state="q1",
    final_states={"q8"},
)
big_nfa.table
big_nfa.show_diagram("CGC")
          [Accepted]                         
Step: Current state: Input symbol: New state:
1                →q1             C         q4
2                 q4             G         q5
3                 q5             C        *q8

alt text

Authors

License

This project is licensed under the MIT License - see the LICENSE.md file for details

Acknowledgments

Project details


Download files

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

Files for visual-automata, version 1.1.1
Filename, size File type Python version Upload date Hashes
Filename, size visual_automata-1.1.1-py3-none-any.whl (15.9 kB) File type Wheel Python version py3 Upload date Hashes View
Filename, size visual-automata-1.1.1.tar.gz (16.1 kB) File type Source Python version None Upload date Hashes View

Supported by

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