⛔️ DEPRECATED - Almost all the functionality of Visual Automata have been integrated directly into the Automata library. Further development will be conducted there.
Copyright 2023 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.
Please see CITATION.cff for the full citation information.
Lie Uberg, L. (2021). Visual Automata (Version 1.1.1) [Computer software]. https://github.com/lewiuberg/visual-automata
@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}
}pip install automata-lib
pip install pandas
pip install graphviz
pip install colormath
pip install jupyterlab
Import needed classes.
from automata.fa.dfa import DFA
from visual_automata.fa.dfa import VisualDFADefine 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"},
)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)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
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}
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
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
Import needed classes.
from automata.fa.nfa import NFA
from visual_automata.fa.nfa import VisualNFADefine 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"},
)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)Outputs the transition table for the given DFA.
nfa.table 0 1 λ
→*q0 ∅ q1 q2
q1 {*q0,q2} q2 ∅
q2 ∅ ∅ ∅
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()
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
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
This project is licensed under the MIT License - see the LICENSE.md file for details
- 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.