狀態圖
定義
編輯狀態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