Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings
This repository was archived by the owner on Aug 28, 2023. It is now read-only.

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

License

NotificationsYou must be signed in to change notification settings

lewiuberg/visual-automata

Repository files navigation

Visual Automata

Latest VersionSupported Python versionsDownloadsCoverage

Copyright 2023Lewi Lie Uberg
Released under the MIT license

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

Contents

Citation

Please seeCITATION.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.

fromautomata.fa.dfaimportDFAfromvisual_automata.fa.dfaimportVisualDFA

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   q1q1    q3  *q2*q2   q3  *q2q3   *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   q2q2   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 with00 or11, and is thereforeRejected

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

10011 does end with11, and is thereforeAccepted

dfa.input_check("10011")
          [Accepted]                         Step: Current state: Input symbol: New state:1                →q0             1         q12                 q1             0         q33                 q3             0        *q44                *q4             1         q15                 q1             1        *q2

Show Diagram

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

dfa.show_diagram()

alt text

Theshow_diagram method also accepts input strings, and will return a graph with gradientred arrows forRejected results, and gradientgreen arrows forAccepted 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         q12                 q1             0         q33                 q3             0        *q44                *q4             1         q1

alt text

dfa.show_diagram("10011")
          [Accepted]                         Step: Current state: Input symbol: New state:1                →q0             1         q12                 q1             0         q33                 q3             0        *q44                *q4             1         q15                 q1             1        *q2

alt text

VisualNFA

Importing

Import needed classes.

fromautomata.fa.nfaimportNFAfromvisual_automata.fa.nfaimportVisualNFA

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  q2q1    {*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         ∅  q1q1    {*q0,q2}  q2q2           ∅   ∅
nfa_eliminated.show_diagram()

alt text

Check input strings

101 does not correspond with the pattern10,1010,101010, and is thereforeRejected

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

1010 does correspond with the pattern10,1010,101010, and is thereforeAccepted

nfa.input_check("1010")
          [Accepted]                         Step: Current state: Input symbol: New state:1               →*q0             1         q12                 q1             0       →*q03               →*q0             1         q14                 q1             0       →*q0

Show Diagram

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

nfa.show_diagram()

alt text

Theshow_diagram method also accepts input strings, and will return a graph with gradientred arrows forRejected results, and gradientgreen arrows forAccepted 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         q12                 q1             0         q23                 q2             1          ∅

alt text

nfa.show_diagram("1010")
          [Accepted]                         Step: Current state: Input symbol: New state:1               →*q0             1         q12                 q1             0       →*q03               →*q0             1         q14                 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         q42                 q4             G         q53                 q5             C        *q8

alt text

Authors

License

This project is licensed under the MIT License - see theLICENSE.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

Contributing

Stars

Watchers

Forks

Packages

No packages published

Languages

[8]ページ先頭
©2009-2025 Movatter.jp