有限狀態機

有限狀態機（英語：finite-state machine，縮寫：FSM）又稱有限狀態自動機（英語：finite-state automaton，縮寫：FSA），簡稱狀態機，是表示有限個狀態以及在這些狀態之間的轉移和動作等行為的數學計算模型。

概念和術語

狀態儲存關於過去的資訊，就是說：它反映從系統開始到現在時刻的輸入變化。轉移指示狀態變更，並且用必須滿足確使轉移發生的條件來描述它。動作是在給定時刻要進行的活動的描述。有多種類型的動作：

進入動作（entry action）：在進入狀態時進行
退出動作（exit action）：在退出狀態時進行
輸入動作：依賴於當前狀態和輸入條件進行
轉移動作：在進行特定轉移時進行

FSM（有限狀態機）可以使用上面圖1那樣的狀態圖（或狀態轉移圖）來表示。此外可以使用多種類型的狀態轉移表。下面展示最常見的表示：當前狀態（B）和條件（Y）的組合指示出下一個狀態（C）。完整的動作資訊可以只使用註腳來增加。包括完整動作資訊的FSM定義可以使用狀態表。

**狀態轉移表**
當前狀態→ 條件↓	狀態A	狀態B	狀態C
條件X	…	…	…
條件Y	…	狀態C	…
條件Z	…	…	…

除了建模這裡介紹的反應系統之外，有限狀態自動機在很多不同領域中是重要的，包括電子工程、語言學、電腦科學、哲學、生物學、數學和邏輯學。有限狀態機是在自動機理論和計算理論中研究的一類自動機。在電腦科學中，有限狀態機被廣泛用於建模應用行為、硬體電路系統設計、軟體工程，編譯器、網路協定、和計算與語言的研究。

分類

有兩個不同的群組：接受器／辨識器和變換器。

接受器和辨識器

圖2接受器FSM：解析單詞"nice"

接受器和辨識器（也叫做序列檢測器）產生一個二元輸出，說要麼「是」要麼「否」來回答輸入是否被機器接受。所有FSM的狀態被稱為要麼接受要麼不接受。在所有輸入都被處理了的時候，如果當前狀態是接受狀態，輸入被接受，否則被拒絕。作為規則，輸入是符號（字元）；動作不使用。圖2中的例子展示了接受單詞"nice"的有限狀態自動機，在這個FSM中唯一的接受狀態是狀態7。

機器還可以被描述為定義了一個語言，它包含了這個機器所接受而非拒絕的所有字詞；我們稱這個語言被這個機器接受。通過定義，FSM接受的語言是正規語言 - 就是說，如果一個語言被某個FSM接受，那麼它是正則的（cf. Kleene的定理）。

開始狀態

開始狀態通常用「沒有起點的箭頭」指向它來表示^[1]

圖3：一個FSM的示意圖：檢測二進制數是否含有偶數個0，其中

S_{1}

是接受狀態

接受狀態（或稱最終狀態）是一個機器回報到目前為止，輸入字串屬於它所接受的內容之狀態。狀態圖中通常將其標示為雙圓圈。
開始狀態也可以是接受狀態，此情況下自動機會接受空字串。如果開始狀態不是接受狀態，且沒有可以連到任何接受狀態的箭頭，那麼此自動機就不會「接受」任何輸入。
一個接受狀態的例子如圖3：一台判斷輸入二進位字串是否含有偶數個0的確定有限自動機（DFA）。
S₁ 代表著已經輸入了偶數個0，因此S₁ 即為接受狀態（同時亦為開始狀態）。若輸入含有偶數個0（包含沒有0的字串），則此機器會以接受狀態來結束。
被這台DFA接受的字串，舉例來說是ε（空字串）, 1, 11, 11…, 00, 010, 1010, 10110…等等。

變換器

變換器使用動作基於給定輸入和／或狀態生成輸出。它們用於控制應用。常分為兩種類型：

Moore機

只使用進入動作的FSM，就是說輸出只依賴於狀態。Moore模型的好處是行為的簡單性。圖1的例子展示了一個電梯門的Moore FSM。這個狀態機辨識兩個命令：「command_open」和「command_close」觸發狀態變更。在狀態「Opening」中的進入動作 (E:)開啟電機開門，在狀態「Closing」中的進入動作以反方向開啟電機關門。狀態「Opened」和「Closed」不進行任何動作。它們訊號通知外部世界（比如其他狀態機）情況：「門開著」或「門關著」。

Mealy機

圖4變換器FSM: Mealy模型例子

只使用輸入動作的FSM，就是說輸出依賴於輸入和狀態。Mealy FSM的使用經常導致狀態數目的簡約。在圖4中的例子展示了實現同上面Moore機同樣行為的Mealy FSM（行為依賴於實現的FSM執行模型，比如對虛擬FSM可工作但對事件驅動FSM不行）。有兩個輸入動作（I:）：「開啟電機關門如果command_close下達」和「逆向開啟電機開門如果command_open下達」。

在實踐中經常使用混合模型。

進一步可區分為確定型（DFA）和非確定型（NDFA、GNFA）自動機。在確定型自動機中，每個狀態對每個可能輸入只有精確的一個轉移。在非確定型自動機中，給定狀態對給定可能輸入可以沒有或有多於一個轉移。這個區分在實踐而非理論中更有用，因為存在演算法把任何NDFA轉換成等價的DFA，儘管這種轉換一般會增加自動機的複雜性。

只有一個狀態的FSM叫做組合FSM並只使用輸入動作。這個概念在多個FSM要一起工作的情況下是有用的，這時把純組合部分看作一種形式的FSM來適合設計工具可能是方便的。

FSM邏輯

圖5 FSM邏輯

FSM的下一個狀態和輸出是由輸入和當前狀態決定的。FSM邏輯在圖5中展示。

數學模型

依據類型不同有多種定義。接受器有限狀態機是五元組 $(\Sigma ,S,s_{0},\delta ,F)$ ，這裡的：

$\Sigma$ 是輸入字母表（符號的非空有限集合）。
$S$ 是狀態的非空有限集合。
$s_{0}$ 是初始狀態，它是 $S$ 的元素。在非確定有限狀態自動機中， $s_{0}$ 是初始狀態的集合。
$\delta$ 是狀態轉移函式： $\delta :S\times \Sigma \rightarrow S$ 。
$F$ 是最終狀態的集合， $S$ 的（可能為空）子集。

變換器有限狀態自動機是六元組 $(\Sigma ,\Gamma ,S,s_{0},\delta ,\omega )$ ，這裡的：

$\Sigma$ 是輸入字母表（符號的非空有限集合）。
$\Gamma$ 是輸出字母表（符號的非空有限集合）。
$S$ 是狀態的非空有限集合。
$s_{0}$ 是初始狀態，它是 $S$ 的元素。在非確定有限狀態自動機中， $s_{0}$ 是初始狀態的集合。
$\delta$ 是狀態轉移函式： $\delta :S\times \Sigma \rightarrow S$ 。
$\omega$ 是輸出函式。

如果輸出函式是狀態和輸入字母表的函式（ $\omega :S\times \Sigma \rightarrow \Gamma$ ），則定義對應於Mealy模型，它可以建模為Mealy機。如果輸出函式只依賴於狀態 ( $\omega :S\rightarrow \Gamma$ ），則定義對應於Moore模型，它可建模為Moore機。根本沒有輸出函式的有限狀態機叫做半自動機或轉移系統。

最佳化

最佳化一個FSM意味著縮減狀態機的狀態數目，同時保證狀態機能實現同樣功能。一種可能是使用真值表或Moore簡約過程。另一種可能是無環FSA的由下而上演算法（頁面存檔備份，存於網際網路檔案館）。

實現

硬體應用

圖6 4位元TTL計數器的電路圖

在數位電路中，FSM可以用可程式化邏輯裝置、可程式化邏輯控制器、邏輯閘和正反器或繼電器來建造。更明確的說，硬體實現要求暫存器來儲存狀態變數，確定狀態轉移的一塊組合邏輯，和確定FSM輸出的另一塊組合邏輯。一類經典硬體實現是Richards 控制器。

軟體應用

下列概念經常用來建造有有限狀態機的軟體應用：

參考文獻

^ Sipser, Introduction to the Theory of Computation (2006), p. 34

參考書目

Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, ISBN 0-8493-8086-3.
Samek, M., Practical Statecharts in C/C++^{[永久失效連結]}, CMP Books, 2002, ISBN 1-57820-110-1.
Samek, M., Practical UML Statecharts in C/C++, 2nd Edition （頁面存檔備份，存於網際網路檔案館）, Newnes, 2008, ISBN 0-7506-8706-1.
Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
Carroll, J., Long, D. , Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, 1989.
Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
Ginsburg, S., An Introduction to Mathematical Machine Theory. Addison-Wesley, 1962.

外部連結

Description from the Free On-Line Dictionary of Computing^{[永久失效連結]}
NIST Dictionary of Algorithms and Data Structures entry （頁面存檔備份，存於網際網路檔案館）
Hierarchical State Machines （頁面存檔備份，存於網際網路檔案館）
Round-trip Engineering State Machines
Using state machines in practical applications
Flash based demonstration of Finite State Machines being used in regular expressions
"Moore or Mealy model?" （頁面存檔備份，存於網際網路檔案館）關於使用Moore和Mealy模型的區別的細節，包括執行例子

參見

[1] Sipser, Introduction to the Theory of Computation (2006), p. 34

[1]