Visual Automata
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
Finite Automaton (FA)
VisualDFA
Importing
Import needed classes.
from automata.fa.dfa import DFA
from visual_automata.fa.dfa import VisualDFAInstantiating 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()
minimal_dfa = VisualDFA.minify(new_dfa)
minimal_dfa.show_diagram()
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()
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
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
VisualNFA
Importing
Import needed classes.
from automata.fa.nfa import NFA
from visual_automata.fa.nfa import VisualNFAInstantiating 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()
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()
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 ∅
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
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.tablebig_nfa.show_diagram("CGC") [Accepted]
Step: Current state: Input symbol: New state:
1 →q1 C q4
2 q4 G q5
3 q5 C *q8
Authors
License
This project is licensed under the MIT License - see the LICENSE.md file for details
Acknowledgments
- Caleb Evans for his work on automata-lib.
- Geir Arne Hjelle, Michal Porteš, Bart Willems, and Blaise Pabon for their general counsel.
- Dr. Seifedine Kadry. My Further Discrete Mathematics professor at Noroff University College, for teaching me Automata.
- JFLAP for their work on a GUI based Automata application.