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

• Visual Automata
  • Contents
  • Prerequisites
  • Installing
  • Finite Automaton (FA)
    • VisualDFA
      • Importing
      • Instantiating DFAs
      • Converting
      • Transition Table
      • Minimal-DFA
      • Check input strings
      • Show Diagram
    • VisualNFA
      • Importing
      • Instantiating NFAs
      • Converting
      • Transition Table
      • Eliminate lambda/epsilon
      • Check input strings
      • Show Diagram
  • Authors
  • License
  • Acknowledgments

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()

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 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()

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

Authors

• Lewi Lie Uberg - uberg.me

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š, and Bart Willems 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.