Implementation of finite-state machines and exportation to dot format
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.
pip3 install fsmdot
With the fsmdot library, you can create two different types of finite-state machine:
A finite-state machine is represented by a quintuple (Q, S, T, q0, F) where:
This is how to create a deterministic finite automaton.
from fsmdot.dfa import Dfa
Q = {'S1', 'S2'}
S = {'0', '1'}
d = {
'S1': {
'0': 'S2',
'1': 'S1'
},
'S2': {
'0': 'S1',
'1': 'S2'
}
}
q0 = 'S1'
F = {'S1'}
a = Dfa(Q, S, d, q0, F)
This is the result:
a.print_table()
+---------+-----+-----+
| | 0 | 1 |
+=========+=====+=====+
| -> * S1 | S2 | S1 |
+---------+-----+-----+
| S2 | S1 | S2 |
+---------+-----+-----+
This is the result:
print(a.accept('11110'))
print(a.accept('110110110101'))
False
True
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):
G = a.dot_graph()
Result:
print(G.to_string())
G.write('graph1_dfa.dot')
File graph1_dfa.dot:
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];
}
You can also create nondeterministic finite automatons using the Nfa class.
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:
Result:
# Calculations of epsilon closure
for state in Q:
print(state, a.epsilon_closure(state))
1 {1, 2, 3}
2 {2}
3 {2, 3}
4 {4}
State-transition table of dfa:
# Conversion to DFA
dfa = a.to_dfa()
dfa.print_table()
G2 = dfa.dot_graph()
G2.write('graph6_dfa.dot')
File graph6_dfa.dot:
+----------------+--------+--------+
| | 0 | 1 |
+================+========+========+
| -> * {1, 2, 3} | {2, 4} | {2, 4} |
+----------------+--------+--------+
| * {2, 3} | {4} | {2, 4} |
+----------------+--------+--------+
| * {2, 4} | {2, 3} | {2, 4} |
+----------------+--------+--------+
| * {4} | {2, 3} | {} |
+----------------+--------+--------+
To see how the library works, look at the examples in the examples folder.