rohaquinlop/automathon

A Python library for simulating and visualizing finite automata

automathon

A Python library for simulating and visualizing finite automata.

---

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

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

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

---

Requirements

• Python >= 3.10
• You also need to install Graphviz on your computer (download page, installation procedure for Windows, archived versions).Make sure that the directory containing the dot executable is on your systems’ path.

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

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.

# 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

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

automathon's Issues

Reduce the cognitive complexity

Reduce the cognitive complexity of the actual functions

Consider update NFA definition

According to the formal definition of the NFA that is mentioned in the book Automata and Computability, the NFA contains multiple start states instead of one single initial state as is defined here in the library.

To maintain the formal equality, it is important to consider this as a refactor of the NFA definition.

Improve the code quality

Improve the code quality

[graphviz] Please enable graphviz customization interface or options tweaking resulting graph

I've used the tool to generate a cartesian product of 3 finite automata, but the resulting graph is huge and when I try to view the picture, it becomes problematic to understand what is happening because the font is very small and the graph nodes themselves are too huge. It would be great if we had the option to select those graph parameters, or even better, introduce some python graphviz interface to be able to configure the graph plot settings to our preferences.

Add new algorithms

Add the following algorithms:

DFA:

• intersection
• difference
• symmetric_difference

NFA:

• intersection

Implement algorithm that returns a DFA

automathon/automathon/finiteAutomata/nfa.py

Line 177 in 06b9858

dot = Digraph(name=fileName, format='png')

Update license to MIT

Remove unused dependencies

Find unused dependencies and remove them

Add minimize function to DFA class

Explore implementations and add the minimize function to the DFA class, this function already exists in the NFA class.
Consider reading the book Automata Theory: An Algorithmic Approach used by @tchaumeny in his article.

Allow states to be any immutable object (not just strings)

Thanks for your library that I have used to illustrate an article about DFA (see here)!

I actually wanted to use integers to define the states and I found that this is not possible (it fails when calling automata.view(...)), is there any specific reason for this restriction?

It seems that any hashable object could be a state and the graphviz representation could just use str().

Refactor code and rename variables names

Change the format to lowercase on variables names.

Create a docs website

Explore the different options to create a docs website with all the information about this library

Upgrade Bazel's version

Upgrade to the latest rules_python and organize the project structure

Update doc

Update documentation with the new methods

Update documentation

Considering some of the changes that were made during the code refactoring, it is necessary to update the documentation

Update CI to deploy

Similar as I'm doing in complexipy make use of GitHub actions to deploy directly to PyPI

Checkout hypothesis

Checkout python library for testing called hypothesis

Make use of dataclasses

Refactor DFA and NFA definition to make use of dataclasses, replace __init__ with dataclasses.

Refac this...

def __init__(self, name: str, unit_price: float, quantity_on_hand: int = 0):
    self.name = name
    self.unit_price = unit_price
    self.quantity_on_hand = quantity_on_hand

to this...

from dataclasses import dataclass

@dataclass
class InventoryItem:
    """Class for keeping track of an item in inventory."""
    name: str
    unit_price: float
    quantity_on_hand: int = 0

    def total_cost(self) -> float:
        return self.unit_price * self.quantity_on_hand

Incorrect removal of epsilon transitions

Hi,

Thanks for the library!

I generate an NFA with the following data and attempt to remove epsilon transitions.

The result is incorrect: in the produced DFA, it becomes possible to jump from A to D without passing through B and C.

Another issue I've found is that if there are two mirroring epsilon transitions, i.e. from 1 to 2 and from 2 to 1, attempting to remove epsilon transitions breaks with a max recursion error.

Any idea what's happening? If need be I could potentially help with a fix!

Thanks