狀態圖

狀態器是有限狀態自動機的圖形表示。另一種可能的表示是狀態轉移表。狀態圖有很多形式，它們有稍微的差異並有不同的語義。

定義

有限狀態自動機的狀態圖是由下列元素構成的有向圖：

狀態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 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

相關條目

• 算法狀態機