状态图

状态器是有限状态自动机的图形表示。另一种可能的表示是状态转移表。状态图有很多形式，它们有稍微的差异并有不同的语义。

定义

有限状态自动机的状态图是由下列元素構成的有向图:

状态 Q: 表示为其中标记着唯一性指示符号或字的圆圈的顶点的有限集合(Booth (1967) p. 69, Hopcroft 与 Ullman (1979) p. 16, Sipser (2006) p. 34)。

输入符号 Σ: 输入“符号”或指示符的有限搜集 Σ (Booth, Hopcroft 和 Ullman, Sipser)。对于确定有限状态自动机 (DFA), 非确定有限状态自动机 (NFA), 广义非确定有限状态自动机 (GNFA), 或 Moore机，输入被标记在每个边上，通常靠近发起状态。对于 Mealy机，用斜杠“/”分隔的输入和输出都标记在每个边上:

Mealy 输入和输出标记在一个边(箭头)上:“1/0”指示符号“1”导致符号“0”作为输出。

输出符号 Z: 输出“符号”或指示符的有限搜集(Booth, Hopcroft 与 Ullman, Sipser)。对于 Mealy机，如上所述输入和输出被标记在每个边上。对于 Moore机状态的输出通常写在状态的圆圈内，同状态的指示符用斜杠“/” 分隔。

例子: 如果一个状态有一些输出(比如 "a= motor counter-clockwise=1, b= caution light inactive=0")在图中应反映出来: 比如“q5/1,0”指示状态 q5 带有输出 a=1, b=0。这个指示符将写在状态的圆圈内。

“输出函数 ω”: 表示从输入符号 Σ × 状态 Q 到输出符号 Z 的映射 ω(Booth)。

边 δ: 表示(由标记在“边”上的符号所标识的)输入所导致的在两个状态间的“转移”。边通常绘制为从当前状态到下一个状态的有向箭头。δ 表示输入符号 Σ × 状态 Q 到输出符号 Z 的映射(Booth, Hopcroft 与 Ullman, Sipser)。

开始状态 q₀: (下面例子中没有展示)。开始状态 q₀ 通常表示“用没有起点的箭头指向”(cf Sipser (2006) p. 34, Hopcroft 与 Ullman (1979) p. 16)。在旧课本中(比如 Booth (1969), McCluskey (1965), Hill 与 Peterson (1974)) 开始状态不展示必须从文本中推断。

接受状态 F: 如果用到的话 -- 用来指示接受状态的双重圆圈的搜集(Hopcroft 与 Ullman, Sipser)。 接受状态也叫做“最终状态”(cf Hopcroft 与 Ullman (1979) Figure 2.15, p. 33)。

例子

DFA, NFA, GNFA, 或 Moore 机

S₁ 和 S₂ 是状态并且 S₁ 是接受状态。每个边都标记着输入。

Mealy 机

S₀, S₁ 和 S₂ 是状态。每个边都标记着 "j / k"，这里的 j 是输入而 k 是输出。

引用

• SCXML an XML language that provides a generic state-machine based execution environment based on Harel statecharts.

• Michael Sipser (2006), Introduction to the Theory of Computation, Second Edition, Thomson Course Technology, Boston. ISBN-13: 978-0-534-95097-2, ISBN-10: 0-534-95097-3.

• John Hopcroft and Jeffrey Ullman (2002) Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company, Reading Mass, ISBN 0-201-02988-X.

• Taylor Booth (2002) Sequential Machines and Automata Theory, John Wiley and Sons, New York. Library of Congress Catalog Card Number: 67-25924.

外部链接

• Round-trip Engineering State Chart - StateWizard: a ClassWizard-like round-trip UML dynamic modeling/development open source framework and tool running in popular IDEs.
• D. Harel. Statecharts: A visual formalism for complex systems. Science of Computer Programming, 8(3):231--274, June 2002.
• Introduction to UML 2 State Machine Diagrams by Scott W. Ambler
• UML 2 State Machine Diagram Guidelines by Scott W. Ambler
• Modelling and verification using UML statecharts, Drusinsky, D., Elsevier, 2006, [1]
• Practical Statecharts in C/C++ by Miro Samek