Skip to content

rohaquinlop/automathon

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

automathon

automathon

A Python library for simulating and visualizing finite automata.

Test Quality Gate Package version


Documentation: https://rohaquinlop.github.io/automathon/

Source Code: https://github.com/rohaquinlop/automathon

PyPI: https://pypi.org/project/automathon/


Requirements

Installation

pip install automathon

Upgrade

pip install automathon --upgrade

Example

Here is are some examples about what you can do with automathon, you can check the documentation about Deterministic Finite Automata and Non-Deterministic Finite Automata to know more about the functions and methods that are available.

DFA - Deterministic Finite Automata

DFA Visualization

This image was created using automathon.

Let's create the previous automata using the library:

from automathon import DFA
q = {'q0', 'q1', 'q2'}
sigma = {'0', '1'}
delta = { 'q0' : {'0' : 'q0', '1' : 'q1'},
          'q1' : {'0' : 'q2', '1' : 'q0'},
          'q2' : {'0' : 'q1', '1' : 'q2'}
        }
initial_state = 'q0'
f = {'q0'}

automata = DFA(q, sigma, delta, initial_state, f)

Verify if the automata is valid

automata.is_valid()    # True

In this case, the automata is valid but if it wasn't, the library would raise an exception with the error message.

Errors

Errors that the library can raise are:

  • SigmaError:

    • The automata contain an initial state, or a final state that's not defined in Q.
    • The automata contain a delta transition that's not defined in Q nor Sigma.
  • InputError:

    • The automata is trying to consume a letter that's not defined in sigma.

Verify if the automata accept a given string

automata.accept("001001")  # True
automata.accept("00100")   # False

Get the automata's complement

not_automata = automata.complement()
not_automata.accept("00100")    #True

Note that this function returns a new automata, it doesn't modify the original one.

Visualize the automata

For both, DFA and NFA, the view method enables to visualize the automaton, receives as parameter a String as the file name for the png and svg files.

More information about the graphviz attributes here.

DFA Visualization

# Default styling
automata.view("DFA Visualization")

# If you want to add custom styling, you can use the following

automata.view(
    file_name="DFA Custom Styling",
    node_attr={'fontsize': '20'},
    edge_attr={'fontsize': '20pt'}
)

If you want to explore more about the functions and methods of the DFA class, you can check the DFA documentation. And if you want to know more about the NFA class, you can check the NFA documentation.

NFA - Non-Deterministic Finite Automata

Image taken from: r9paul.org

Representing the previous automata

from automathon import NFA

## Epsilon Transition is denoted by '' -> Empty string
q = {'q1', 'q2', 'q3', 'q4'}
sigma = {'0', '1'}
delta = {
    'q1' : {
            '0' : {'q1'},
            '1' : {'q1', 'q2'}
            },
    'q2' : {
            '0' : {'q3'},
            '' : {'q3'}
            },
    'q3' : {
            '1' : {'q4'},
            },
    'q4' : {
            '0' : {'q4'},
            '1' : {'q4'},
            },
}
initial_state = 'q1'
f = {'q4'}

automata = NFA(q, sigma, delta, initial_state, f)

Verify if the automata is valid

automata.is_valid()  # True

Verify if the automata accept a string

automata.accept("0000011")   #True
automata.accept("000001")    #False

Get the automata's complement

not_automata = automata.complement()
not_automata.accept("000001")    #True

Visualize the automata

NFA Visualization

# Default styling
automata.view("NFA Visualization")

# If you want to add custom styling, you can use the following

automata.view(
    file_name="NFA Custom Styling",
    node_attr={'fontsize': '20'},
    edge_attr={'fontsize': '20pt'}
)

License

This project is licensed under the terms of the MIT license.