状态图

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

 定义 

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

状态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）。

开始状态q0（下面例子中没有展示）
开始状态q0通常表示“用没有起点的箭头指向”（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机 

S1和S2是状态并且S1是接受状态。每个边都标记着输入。
DFAexample.svg

 Mealy机 

S0, S1和S2是状态。每个边都标记着"j / k"，这里的j是输入而k是输出。
一个简单的Mealy机的状态图

 引用 

 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 978-0-534-95097-2

 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,  
 Practical Statecharts in C/C++ by Miro Samek

 相关条目 
 算法状态机

Category:图表
Category:自动机
Category:统一建模语言图表