Python State Machine

A Python class implementation of deterministic finite-state machines.

Format

Using an finite-state automaton that checks if a binary number is divisible by three as an example, DFAs will be represented as follows:

divisible = {
    'S0': {0: 'S0', 1: 'S1', 'start': True , 'accept': True },
    'S1': {0: 'S2', 1: 'S0', 'start': False, 'accept': False},
    'S2': {0: 'S1', 1: 'S2', 'start': False, 'accept': False}
}

Each key represents a different state, and each value contains a dictionary with the following information: the new state upon reception of a particular input, whether a state is the starting state, and whether a state is an accepting state. For NFAs, if an input has multiple new states, the new states will be represented as a list. ε-moves will be represented as a new key.

Additionally, the matrix representation of the directed graph corresponding to the aforementioned FSA is as follows:

div_matrix = [
    [0, 1, ()],
    [1, (), 0],
    [(), 0, 1]
]

The ij-th entry indicates which symbols cause a transition from the i-th state to the j-th state. If an entry is the empty tuple, nothing causes a transition between the two. Notation adapted from: 'Generalized transition matrix of a sequential machine and its applications' - T.Kameda

Methods

Name	Functionality
div_by	Creates a StateMach object that determines if a number in a given base is divisible by num.
combine	Combines the given NFA states into one state.
fsa_min	Minimizes a DFA by using the table-filling algorithm.
remove	Removes unreachable states of an FSA.
graph	Creates a Graphviz Digraph object representing the FSA.
norm	Normalizes the FSA by renaming states to fit the aforementioned convention.

Future Updates

• Powerset construction
• ε-closures
• NFA state combination
• Transition matrices