Skip to content
master
Switch branches/tags
Code

Latest commit

 

Git stats

Files

Permalink
Failed to load latest commit information.
Type
Name
Latest commit message
Commit time
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

Citation

Please see CITATION.cff for the full citation information.

APA

Lie Uberg, L. (2021). Visual Automata (Version 1.1.1) [Computer software]. https://github.com/lewiuberg/visual-automata

BibTex

@software{Lie_Uberg_Visual_Automata_2021,
author = {Lie Uberg, Lewi},
license = {MIT},
month = {4},
title = {{Visual Automata}},
url = {https://github.com/lewiuberg/visual-automata},
version = {1.1.1},
year = {2021}
}

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

About

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

Topics

Resources

License

Packages

No packages published

Languages