Finite-state machines with dot

PyPI
PyPI - Python Version

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:

Graph 1

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:

Graph 6 NFA

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:

Graph 6 NFA

Examples

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

References

Author

Quentin Deschamps

License

MIT