怎么画一个有限状态机

2024-02-23 08:58:02
开发
36

有限状态机对于证明某些问题是可计算的（或不可计算的）是必要的。
由于我目前正在学习有关它们的一些知识，我希望能够自动绘制这些有限自动机。我将使用 graphviz。

Nondeterministic finite-state machine ¶

在这里插入图片描述该图像是从 gv 文件创建的。我将其另存为 fsm.gv：

digraph finite_state_machine {
    rankdir=LR;
    size="8,5"

    node [shape = doublecircle]; S;
    node [shape = point ]; qi

    node [shape = circle];
    qi -> S;
    S  -> q1 [ label = "a" ];
    S  -> S  [ label = "a" ];
    q1 -> S  [ label = "a" ];
    q1 -> q2 [ label = "b" ];
    q2 -> q1 [ label = "b" ];
    q2 -> q2 [ label = "b" ];
}

要创建图形（或非确定性有限状态机的图片），您必须在 Ubuntu Linux 中输入以下命令：

dot -Tpng fsm.gv -o myFiniteStateMachine.png

Deterministic finite-state machine ¶

在这里插入图片描述

digraph finite_state_machine {
    rankdir=LR;
    size="8,5"

    node [shape = doublecircle, label="{f}", fontsize=12] f;
    node [shape = doublecircle, label="{q2, f}", fontsize=10] q2f;

    node [shape = circle, label="S", fontsize=14] S;
    node [shape = circle, label="{q1}", fontsize=12] q1;
    node [shape = circle, label="{q2}", fontsize=12] q2;

    node [shape = point ]; qi
    qi -> S;

    S   -> q1  [ label = "a" ];
    S   -> q2f [ label = "b" ];
    S   -> q2  [ label = "c" ];

    q1  -> q2  [ label = "b" ];

    q2f -> f   [ label = "b" ];
    q2f -> q2  [ label = "c" ];

    q2  -> f   [ label = "b" ];
    q2  -> q2  [ label = "c" ];
}