状态图

状态图是计算机科学和相关字段中用于描述系统行为的一种图。状态图要求所描述的系统由有限数量的状态组成；有时，确实是这种情况，而在其他时候，这是一个合理的抽象。存在许多形式的状态图，它们略有不同，具有不同的语义。

概述

状态图用于对系统行为进行抽象描述。这种行为由一系列可能发生在一个或多个可能的状态中的事件进行分析和表示。特此“每个图通常代表单个类的对象，并通过系统跟踪其对象的不同状态”。

状态图可用于以图形方式表示有限状态机器（也称为有限自动机）。克劳德·香农（Claude Shannon）和沃伦·韦弗（Warren Weaver）在1949年的《交流数学理论》一书中介绍了这一点。另一个来源是泰勒·布斯（Taylor Booth）在他1967年的《顺序机器和自动机理论》中。另一个可能的表示是状态转变表。

定向图

有限自动机（FA）的状态图的经典形式是有针对以下元素（q，σ，z，δ，q ₀ ，f）的有向图：

• 顶点问：一组有限的状态，通常由圆圈表示，并用独特的指定符号或其中写的单词标记
• 输入符号σ ：输入符号或指定器的有限集合
• 输出符号z ：输出符号或指定器的有限集合

输出函数ω表示有序对输入符号和状态对输出符号的映射，以数学表示为ω ： σ × Q → z 。

• 边缘δ ：表示由输入引起的转变（由其边缘上绘制的符号识别）。通常将边缘绘制为从现在状态到下一个状态的箭头。该映射描述了在特定符号输入上发生的状态过渡。这是数学上写为δ ： q × σ → q的，因此，FA定义中的δ（过渡函数）均由由边缘连接的两对顶点和代表此FA的图的边缘上的符号给出。 。在FA的定义中，项目δ（q，a）= p是指输入符号A下的q下的状态，向状态p的过渡发生在该计算机中。在代表该FA的图中，这是由一个边缘表示，该边缘由Q标记的顶点指向到由p标记的顶点。
• 启动状态Q ₀ ：（以下示例未显示）。启动状态_q0∈Q通常由没有原点指向状态的箭头表示。在较旧的文本中，未显示开始状态，必须从文本中推断出来。
• 接受状态F ：如果使用，例如用于接受自动机，f∈Q是接受状态。通常将其绘制为双圆圈。有时，接受状态函数为“ f inal”（停止，被困）状态。

对于确定性有限自动机（DFA），非确定性有限自动机（NFA），广义的非确定性有限自动机（GNFA）或Moore机器，在每个边缘上表示输入。对于淡淡的机器，输入和输出在每个边缘都表示，用斜杠“/”：“：” 1/0“表示遇到符号” 1“ 1”时的状态变化，从而导致符号“ 0”要输出。对于摩尔机器，该州的输出通常写在州的圆圈内，也与州的指定者分开，斜线“/”。还有一些将这两个符号结合在一起的变体。

例如，如果状态具有许多输出（例如“ a =电动机逆时针= 1，b =谨慎轻效= 0”）该图应反映这一点：例如输出a = 1，b = 0。该指定者将写在州圈内。

示例：DFA，NFA，GNFA或Moore Machine

S ₁和S ₂是状态， S ₁是接受状态或最终状态。每个边缘都标有输入。此示例显示了包含偶数零数的二进制数字的受体。

示例： Mealy Machine

s ₀ ， s ₁和s ₂是状态。每个边缘都用“ J / K ”标记，其中j是输入， k是输出。

Harel Statechart

由计算机科学家戴维·哈雷尔（David Harel）发明的Harel Statecharts正在广泛使用，因为变体已成为统一建模语言（UML）的一部分。该图类型允许对超级遗产，正交区域和活动进行建模，作为状态的一部分。

经典状态图需要为定义状态的参数的每个有效组合创建不同的节点。这可能会导致大量的节点和最简单系统（状态和过渡爆炸）以外的所有节点之间的过渡。这种复杂性降低了状态图的可读性。使用Harel Statecharts，可以在Statechart中建模多个跨职能状态图。这些跨职能状态机器中的每一个都可以在内部过渡，而不会影响Statechart中的其他状态机器。 Statechart中每个跨功能状态机的当前状态定义了系统的状态。 Harel Statechart等同于状态图，但它提高了所得图的可读性。

替代语义

还有其他一组语义可以代表状态图。例如，有一些用于建模和设计嵌入式控制器逻辑的工具。这些图，例如Harel的原始状态机，支持层次嵌套的状态，正交区域，状态行动和过渡行动。

国家图与流程图

国家机器形式主义的新来者通常将状态图与流程图混淆。下图显示了状态图与流程图的比较。状态计算机（面板（A））对明确事件执行操作。相反，流程图（面板（B））不需要明确的事件，而是在活动完成后自动从节点中的节点转换为节点。

流程图的节点是诱导状态图中的边缘。原因是流程图中的每个节点都代表一个程序命令。程序命令是要执行的操作。因此，它不是状态，而是应用于程序状态时，它会导致过渡到另一个状态。

更详细地说，源代码列表代表一个程序图。执行程序图（解析和解释）导致状态图导致。因此，每个程序图都诱导状态图。程序图转换为其关联的状态图称为程序图的“展开”。

程序图是命令序列。如果不存在变量，则状态仅由程序计数器组成，该计数器会跟踪我们在执行过程中的程序中的位置（下一个要应用的下一个命令）。

在这种情况下，在执行命令之前，程序计数器处于某个位置（在执行命令之前状态）。执行命令将程序计数器移至下一个命令。由于程序计数器是整个状态，因此执行命令更改状态。因此，命令本身对应于两个状态之间的过渡。

现在考虑整个情况，当存在变量并受到执行程序命令的影响时。然后，在不同的程序计数位置之间，由于执行的命令，程序计数器不仅会更改程序，而且变量也可能会更改值。因此，即使我们重新访问某些程序命令（例如循环中），这并不意味着该程序处于同一状态。

在上一种情况下，该程序将处于同一状态，因为整个状态只是程序计数器，因此，如果程序对立面到同一位置（下一个命令），则足以指定我们处于同一状态。但是，如果状态包含变量，则如果这些变量更改值，我们可以位于具有不同变量值的同一程序位置，这意味着在程序状态空间中的不同状态。术语“展开”源自从程序图产生状态图时的位置乘法。

自我过渡是一种过渡，最初和最终状态相同。

一个代表性的示例是do循环增加一些计数器，直到它溢出并再次变为0。尽管DO循环迭代执行相同的增量命令，因此程序图执行一个周期，但在其状态空间中不是一个周期，而是行。这是由于状态是程序位置（此处骑自行车）与计数器值相结合的结果，该计数器值严格增加（直到溢出），因此依次访问了不同的状态，直到溢出为止。溢出后，计数器再次变为0，因此在状态空间中重新审视初始状态，在状态空间中关闭一个周期（假设计数器初始化为0）。

上图试图通过将状态图的弧与流程图的处理阶段对准来表明角色的逆转。

您可以将流程图与制造中的组装线进行比较，因为流程图描述了某些任务从头到尾的进程（例如，将源代码输入转换为编译器的对象代码输出）。状态机通常没有这种进展的概念。例如，与处于“打开”状态相比，本文顶部显示的门状机器在“封闭”状态时并不是更高级的阶段。它只是对开放/关闭事件的反应不同。状态机中的状态是指定特定行为的有效方法，而不是处理阶段。

其他扩展

一个有趣的扩展是允许ARC从任意数量的任何状态流动。这仅当允许系统一次地处于多个状态时才有意义，这意味着单个状态仅描述整体全球状态的条件或其他部分方面。由此产生的形式主义被称为培养皿网。

另一个扩展程序允许在Harel Statecharts中集成流程图。此扩展支持既是事件驱动和工作流驱动的软件的开发。

也可以看看

• 大卫·哈雷尔（David Harel）
• 德拉肯
• SCXML XML语言，基于Harel Statecharts提供了基于州机器的执行环境。
• UML状态机
• Yakindu Statechart工具是用于建模状态图（Harel Statecharts，Mealy Machines，Moore Machines），仿真和源代码生成的软件。