有限状态自动机

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

## 概念和術語

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

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

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

　
: :

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

## 分類

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

### 接受器和辨識器

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

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

#### 開始狀態

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

　
:

**接受狀態**（或稱**最終狀態**）是一個機器回報到目前為止，輸入字串屬於它所接受的內容之狀態。狀態圖中通常將其標示為雙圓圈。 
開始狀態也可以是接受狀態，此情況下自動機會接受空字串。如果開始狀態不是接受狀態，且沒有可以連到任何接受狀態的箭頭，那麼此自動機就不會「接受」任何輸入。 
一個接受狀態的例子如圖 3：一台判斷輸入二進位字串是否含有偶數個 0 的 確定有限自動機（DFA）。 
_S_1 代表著已經輸入了偶數個 0，因此 _S_1 即為接受狀態（同時亦為開始狀態）。若輸入含有偶數個 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 機

只使用輸入動作的 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 邏輯

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 的由下而上演算法 （頁面存檔備份，存於網際網路檔案館）。

## 實現

### 硬體應用

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

### 軟體應用

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

* 事件驅動 FSM
* 虛擬 FSM (VFSM)
* 基於自動機編程

## 參考文獻

## 參考書目

* 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 模型的區別的細節，包括執行例子

## 參見

* 自動機
* 確定有限狀態自動機
* 非確定有限狀態自動機
* Mealy 機
* Moore 機
* 演算法狀態機