项目作者: Quentin18

项目描述 :
Implementation of finite-state machines and exportation to dot format
高级语言: Python
项目地址: git://github.com/Quentin18/fsmdot.git
创建时间: 2020-11-08T13:07:01Z
项目社区:https://github.com/Quentin18/fsmdot

开源协议:MIT License

下载


Finite-state machines with dot

Build Status
PyPI
PyPI - Python Version
License: MIT

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:
    1. 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:
    1. from fsmdot.dfa import Dfa
  • Create the set of states:
    1. Q = {'S1', 'S2'}
  • Create the set of symbols representing the input alphabet:
    1. S = {'0', '1'}
  • Create the transitions as a dictionnary.
    1. d = {
    2. 'S1': {
    3. '0': 'S2',
    4. '1': 'S1'
    5. },
    6. 'S2': {
    7. '0': 'S1',
    8. '1': 'S2'
    9. }
    10. }
  • Create the initial state (the state must be in Q):
    1. q0 = 'S1'
  • Create the set of accept states (the states must be in Q):
    1. F = {'S1'}
  • Then, you can create the DFA:
    1. a = Dfa(Q, S, d, q0, F)
  • To see the state-transition table, use the print_table method:
    1. a.print_table()
    This is the result:
    1. +---------+-----+-----+
    2. | | 0 | 1 |
    3. +=========+=====+=====+
    4. | -> * S1 | S2 | S1 |
    5. +---------+-----+-----+
    6. | S2 | S1 | S2 |
    7. +---------+-----+-----+
  • You can check if a string is accepted by the automata using the accept method:
    1. print(a.accept('11110'))
    2. print(a.accept('110110110101'))
    This is the result:
    1. False
    2. True
  • To create the dot graph representing the DFA, use the dot_graph method. It creates a graph object.
    1. 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):
    1. print(G.to_string())
    2. G.write('graph1_dfa.dot')
    Result:
    1. strict digraph FSM {
    2. graph [rankdir=LR];
    3. node [shape=circle];
    4. null [shape=point];
    5. S1 [shape=doublecircle];
    6. null -> S1;
    7. S1 -> S1 [label=1];
    8. S1 -> S2 [label=0];
    9. S2 -> S1 [label=0];
    10. S2 -> S2 [label=1];
    11. }
    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:

  1. from fsmdot.nfa import Nfa
  2. Q = {1, 2, 3, 4}
  3. S = {Nfa.EPSILON, '0', '1'}
  4. d = {
  5. 1: {
  6. Nfa.EPSILON: {3},
  7. '0': {2}
  8. },
  9. 2: {
  10. '1': {2, 4}
  11. },
  12. 3: {
  13. Nfa.EPSILON: {2},
  14. '0': {4}
  15. },
  16. 4: {
  17. '0': {3}
  18. }
  19. }
  20. q0 = 1
  21. F = {3, 4}
  22. a = Nfa(Q, S, d, q0, F)
  23. a.print_table()
  24. G = a.dot_graph()
  25. G.write('graph6_nfa.dot')

State-transition table:

  1. +------+-----+--------+-----+
  2. | | 0 | 1 | ε |
  3. +======+=====+========+=====+
  4. | -> 1 | {2} | {} | {3} |
  5. +------+-----+--------+-----+
  6. | 2 | {} | {2, 4} | {} |
  7. +------+-----+--------+-----+
  8. | * 3 | {4} | {} | {2} |
  9. +------+-----+--------+-----+
  10. | * 4 | {3} | {} | {} |
  11. +------+-----+--------+-----+

File graph6_nfa.dot:

Graph 6 NFA

  • To calculate the epsilon closure of a state, use the epsilon_closure method.
    1. # Calculations of epsilon closure
    2. for state in Q:
    3. print(state, a.epsilon_closure(state))
    Result:
    1. 1 {1, 2, 3}
    2. 2 {2}
    3. 3 {2, 3}
    4. 4 {4}
  • To convert a NFA to a DFA, use the to_dfa method. It uses the powerset construction.
    1. # Conversion to DFA
    2. dfa = a.to_dfa()
    3. dfa.print_table()
    4. G2 = dfa.dot_graph()
    5. G2.write('graph6_dfa.dot')
    State-transition table of dfa:
    1. +----------------+--------+--------+
    2. | | 0 | 1 |
    3. +================+========+========+
    4. | -> * {1, 2, 3} | {2, 4} | {2, 4} |
    5. +----------------+--------+--------+
    6. | * {2, 3} | {4} | {2, 4} |
    7. +----------------+--------+--------+
    8. | * {2, 4} | {2, 3} | {2, 4} |
    9. +----------------+--------+--------+
    10. | * {4} | {2, 3} | {} |
    11. +----------------+--------+--------+
    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