fsmdot 0.0.1

Implementation of finite-state machines and exportation to dot format

Finite-state machines with dot

fsmdot is a Python package to create finite-state machines which can be exported to dot format. It uses the pygraphviz library which is a Python interface to the Graphviz graph layout and visualization package.

Installing

• First, you need to install Graphviz. See how to download it here.
• Then, fsmdot can be installed using pip:

pip3 install fsmdot

Usage

With the fsmdot library, you can create two different types of finite-state machine:

• Deterministic finite automaton (DFA)
• Nondeterministic finite automaton (NFA)

A finite-state machine is represented by a quintuple (Q, S, T, q0, F) where:

• Q is a set of states
• S is a set of input symbols (alphabet)
• d is a dictionnary containing the transitions
• q0 is the initial state
• F is the set of accept states

Deterministic finite automaton

This is how to create a deterministic finite automaton.

• First, we import the Dfa class:

from fsmdot.dfa import Dfa

• Create the set of states:

Q = {'S1', 'S2'}

• Create the set of symbols representing the input alphabet:

S = {'0', '1'}

• Create the transitions as a dictionnary.

d = {
    'S1': {
        '0': 'S2',
        '1': 'S1'
    },
    'S2': {
        '0': 'S1',
        '1': 'S2'
    }
}

• Create the initial state (the state must be in Q):

q0 = 'S1'

• Create the set of accept states (the states must be in Q):

F = {'S1'}

• Then, you can create the DFA:

a = Dfa(Q, S, d, q0, F)

• To see the state-transition table, use the print_table method:

a.print_table()

This is the result:

+---------+-----+-----+
|         |   0 |   1 |
+=========+=====+=====+
| -> * S1 |  S2 |  S1 |
+---------+-----+-----+
|      S2 |  S1 |  S2 |
+---------+-----+-----+

• You can check if a string is accepted by the automata using the accept method:

print(a.accept('11110'))
print(a.accept('110110110101'))

This is the result:

False
True

• To create the dot graph representing the DFA, use the dot_graph method. It creates a graph object.

G = a.dot_graph()

You can print the string representation of the graph using the to_string method or write this content in a file using the write method (see pygraphviz):

print(G.to_string())
G.write('graph1_dfa.dot')

Result:

strict digraph FSM {
	graph [rankdir=LR];
	node [shape=circle];
	null	[shape=point];
	S1	[shape=doublecircle];
	null -> S1;
	S1 -> S1	[label=1];
	S1 -> S2	[label=0];
	S2 -> S1	[label=0];
	S2 -> S2	[label=1];
}

File graph1_dfa.dot:

Nondeterministic finite automaton

You can also create nondeterministic finite automatons using the Nfa class.

• To add epsilon-moves, use the symbol Nfa.EPSILON.

Example:

from fsmdot.nfa import Nfa

Q = {1, 2, 3, 4}
S = {Nfa.EPSILON, '0', '1'}
d = {
    1: {
        Nfa.EPSILON: {3},
        '0': {2}
    },
    2: {
        '1': {2, 4}
    },
    3: {
        Nfa.EPSILON: {2},
        '0': {4}
    },
    4: {
        '0': {3}
    }
}
q0 = 1
F = {3, 4}

a = Nfa(Q, S, d, q0, F)
a.print_table()

G = a.dot_graph()
G.write('graph6_nfa.dot')

State-transition table:

+------+-----+--------+-----+
|      |   0 |      1 |   ε |
+======+=====+========+=====+
| -> 1 | {2} |     {} | {3} |
+------+-----+--------+-----+
|    2 |  {} | {2, 4} |  {} |
+------+-----+--------+-----+
|  * 3 | {4} |     {} | {2} |
+------+-----+--------+-----+
|  * 4 | {3} |     {} |  {} |
+------+-----+--------+-----+

File graph6_nfa.dot:

• To calculate the epsilon closure of a state, use the epsilon_closure method.

# Calculations of epsilon closure
for state in Q:
    print(state, a.epsilon_closure(state))

Result:

1 {1, 2, 3}
2 {2}
3 {2, 3}
4 {4}

• To convert a NFA to a DFA, use the to_dfa method. It uses the powerset construction.

# Conversion to DFA
dfa = a.to_dfa()
dfa.print_table()
G2 = dfa.dot_graph()
G2.write('graph6_dfa.dot')

State-transition table of dfa:

+----------------+--------+--------+
|                |      0 |      1 |
+================+========+========+
| -> * {1, 2, 3} | {2, 4} | {2, 4} |
+----------------+--------+--------+
|       * {2, 3} |    {4} | {2, 4} |
+----------------+--------+--------+
|       * {2, 4} | {2, 3} | {2, 4} |
+----------------+--------+--------+
|          * {4} | {2, 3} |     {} |
+----------------+--------+--------+

File graph6_dfa.dot:

Examples

To see how the library works, look at the examples in the examples folder.

References

• Automata theory
• Finite-state machines
• Deterministic finite automaton
• Nondeterministic finite automaton
• Powerset construction
• DFA minimization

Author

Quentin Deschamps

License

MIT