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

定義

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

狀態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是接受狀態。每個邊都標記着輸入。

Thumb

Mealy機

S0, S1S2是狀態。每個邊都標記着"j / k",這裏的j是輸入而k是輸出。

Thumb

引用

  • 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.

外部連結

相關條目

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.