有限狀態機

有限狀態機（finite-state machine，縮寫：FSM）又稱有限狀態自動機（finite-state automaton，縮寫：FSA），簡稱狀態機，是表示有限個狀態 (電腦科學)以及在這些狀態之間的轉移和動作等行為的數學計算模型。它是一台（真實或假設的）機器，其對於輸入（input）的響應（或輸出）形成於一組狀態（state）和一組用於從某狀態傳遞到另一狀態的規則（rules）。

## 概念和術語

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

進入動作（entry action）：在進入狀態時進行

退出動作（exit action）：在退出狀態時進行

輸入動作：依賴於當前狀態和輸入條件進行

轉移動作：在進行特定轉移時進行

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

當前狀態→條件↓｜狀態A｜狀態B｜狀態C

條件X｜...｜...｜...

條件Y｜...｜狀態C｜...

條件Z｜...｜...｜...

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

## 分類

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

### 接受器和識別器

<image>

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

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

#### 開始狀態

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

<image>

接受狀態（或稱最終狀態）是一個機器回報到目前為止，輸入字串屬於它所接受的內容之狀態。狀態圖中通常將其標示為雙圓圈。

開始狀態也可以是接受狀態，此情況下自動機會接受空字串。如果開始狀態不是接受狀態，且沒有可以連到任何接受狀態的箭頭，那麼此自動機就不會「接受」任何輸入。

一個接受狀態的例子如圖3：一台判斷輸入二進位字串是否含有偶數個0的 確定有限自動機（DFA）。

S1 代表著已經輸入了偶數個0，因此S1 即為接受狀態（同時亦為開始狀態）。若輸入含有偶數個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機

<image>

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

<image>

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的自底向上演算法。

## 實現

### 硬體應用

<image>

在數字電路中，FSM可以用可編程邏輯設備、可編程邏輯控制器、邏輯門和觸發器或繼電器來建造。更明確的說，硬體實現要求寄存器來存儲狀態變量，確定狀態轉移的一塊組合邏輯，和確定FSM輸出的另一塊組合邏輯。一類經典硬體實現是Richards 控制器。

### 軟體應用

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

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

## 外部連結

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