状态图

只能打开和关闭的门的状态图

一个状态图是在计算机科学以及描述系统行为的相关领域。状态图要求所描述的系统由有限数量组成状态;有时，确实是这样，而在其他时候这是合理的抽象。存在许多形式的状态图，它们略有不同，并且具有不同的状态语义.

概述

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

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

定向图

一个定向图

一种经典形式的状态图有限自动机（FA）是定向图具有以下元素（Q，σ，Z，δ，Q0， F）：[2][3]

  • 顶点q：一组有限的状态，通常由圆圈表示，并在其中写有独特的指定符号或文字
  • 输入符号σ：输入符号或指定器的有限集合
  • 输出符号z：输出符号或指定器的有限集合

输出函数ω表示有序对的输入符号和状态对输出符号的映射，以数学形式表示为ω：Σ×问→z.

  • 边缘δ：表示由输入引起的从一个状态到另一个状态的过渡（由其边缘上绘制的符号标识）。通常将边缘绘制为从现在状态到下一个状态的箭头。该映射描述了在特定符号输入上发生的状态转换。这是数学上写的δ：问×Σ→问，因此，FA定义中的δ（过渡函数）均由由边缘连接的一对顶点和表示该FA的图表中的边缘上的符号给出。物品δ（q，a）= p在FA的定义中，意味着来自命名的状态q在输入符号下一个，向国家的过渡p发生在这台计算机中。在代表此FA的图中，这是由标记为边缘的一个从标记的顶点指向q到标记的顶点p.
  • 开始状态q0：（以下示例未显示）。开始状态Q0∈Q通常由没有原点指向状态的箭头表示。在较旧的文本中[2][4]开始状态未显示，必须从文本中推断出来。
  • 接受状态f：如果使用，例如接受自动机，f∈Q是接受状态。通常将其绘制为双圆圈。有时接受状态功能为“Final”（停止，被困）状态。[3]

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

例如，如果一个状态具有许多输出（例如，“ a =电动机逆时针= 1，b =谨慎的光无活动= 0”），则图应反映这一点：例如，“ Q5/1,0”指定输出a = 1，b = 0的状态Q5。该指示符将写在州圈内。

示例：DFA，NFA，GNFA或摩尔机器

s1和s2是州和s1是一个接受状态或a最终状态。每个边缘都标记为输入。此示例显示了包含偶数零数的二进制数字的受体。

DFAexample.svg

例子：Mealy Machine

s0，s1， 和s2是国家。每个边缘都标有“j/k“ 在哪里j是输入和k是输出。

State diagram of a simple Mealy machine

Harel Statechart

图显示了Harel的Statecharts如何贡献面向对象的方法和符号

Harel Statecharts，[5]由计算机科学家发明大卫·哈雷尔（David Harel），由于变体已成为统一的建模语言（UML）。该图类型允许建模超级遗产，正交区域和活动作为国家的一部分。

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

替代语义

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

国家图与流程图

国家机器形式主义的新来者经常混淆状态图和流程图。下图显示了状态图带有流程图。状态机（面板（A））对明确事件执行操作。相反，流程图（面板（B））不需要明确的事件，而是在活动完成后自动从节点中的节点过渡到节点。[9]

State diagram (a) and flowchart (b)

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

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

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

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

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

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

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

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

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

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

其他扩展

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

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

也可以看看

参考

  1. ^存档索引在Wayback Machine
  2. ^一个b泰勒·布斯（Taylor Booth）（1967）顺序机器和自动机理论，约翰·威利（John Wiley）和儿子，纽约。
  3. ^一个b约翰·霍普克罗夫特（John Hopcroft）和杰弗里·乌尔曼（Jeffrey Ullman）（1979）自动机理论，语言和计算简介，Addison-Wesley Publishing Company，Reading Mass，ISBN0-201-02988-X
  4. ^爱德华·J·麦克卢斯基（Edward J.
  5. ^大卫·哈雷尔（David Harel），Statecharts：复杂系统的视觉形式主义。计算机编程科学，8（3）：231–274，1987年6月。
  6. ^Tiwari，A。（2002）。Simulink状态流的形式语义和分析方法。
  7. ^Harel，D。（1987）。复杂系统的视觉形式主义。计算机编程科学，231–274。
  8. ^Alur，R.，Kanade，A.，Ramesh，S。，＆Shashidhar，K.C。（2008）。用于改善Simulink/stateFlow模型的模拟覆盖范围的符号分析。国际嵌入式软件会议（第89-98页）。佐治亚州亚特兰大：ACM。
  9. ^Samek，Miro（2008）。C/C ++中的实用UML Statecharts，第二版：用于嵌入式系统的事件驱动的编程。纽恩斯。 p。 728。ISBN 978-0-7506-8706-5.

外部链接