状态图
外观
(重定向自狀態機圖)
状态器是有限状态自动机的图形表示。另一种可能的表示是状态转移表。状态图有很多形式,它们有稍微的差异并有不同的语义。
定义
[编辑]状态Q
输入符号Σ
- 输入“符号”或指示符的有限搜集Σ(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是接受状态。每个边都标记着输入。
Mealy机
[编辑]S0, S1和S2是状态。每个边都标记着"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 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, [1] (页面存档备份,存于互联网档案馆)
- Practical Statecharts in C/C++[永久失效链接] by Miro Samek
相关条目
[编辑]
|