状态图

维基百科,自由的百科全书
跳转至: 导航搜索

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

定义[编辑]

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

状态Q

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

输入符号Σ

输入“符号”或指示符的有限搜集Σ(Booth, HopcroftUllman, 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机[编辑]

S1S2是状态并且S1是接受状态。每个边都标记着输入。

DFAexample.svg

Mealy机[编辑]

S0, S1S2是状态。每个边都标记着"j / k",这里的j是输入而k是输出。

一个简单的Mealy机的状态图

引用[编辑]

  • SCXML an XML language that provides a generic state-machine based execution environment based on Harel statecharts.
  • Taylor Booth(2002)Sequential Machines and Automata Theory, John Wiley and Sons, New York. Library of Congress Catalog Card Number: 67-25924.

外部链接[编辑]

相关条目[编辑]

統一建模語言(UML) ( · · )
背景

機構Object Management Group (OMG) • UML Partners
個人Grady Booch • Ivar Jacobson • James Rumbaugh 

概念

物件導向物件導向的程式設計 

結構執行者 • 屬性 •  • 元件 • 接口 • 對象 •  

行為活動 • 事件 • 訊息 • 方法 • 操作 • 狀態 • 用例 

關係聚合 • 關聯 • 組合 • 相依 • 廣義化 (or 繼承

其他概念構造型 • 多重性 • 角色 

結構圖
類別圖 • 元件圖 • 複合結構圖 • 部署圖 • 物件圖 • 包圖 

行為圖
活動圖 • 狀態機圖 • 使用個案圖 • 通信圖 • 交互概述圖 • 循序圖 • 時間圖 

主題

關聯式資料庫模型(ERD)比較 • 統一塑模語言術語彙表 • 系統塑模語言(SysML) • UML色碼

角色 時機,間隔
描述 哪一方,地點,事件
工具

UML工具 • Rational 統一過程