狀態機

狀態機是一種用於設計算法的數學抽象。狀態機讀取一組輸入，並根據這些輸入改變到不同的狀態。

狀態是系統在等待執行轉換時所處狀態的描述。轉換是在滿足條件或接收到事件時要執行的一組操作。在狀態圖中，圓圈代表每個可能的狀態，箭頭代表狀態之間的轉換。

檢視最終狀態，您可以瞭解導致該狀態的一系列輸入。

有兩種基本的狀態機型別

確定性有限狀態機

這種型別允許任何允許的輸入只有一個可能的轉換。這就像 `if` 語句一樣，其中 `if x then doThis else doThat` 是不可能的。計算機必須執行兩種選擇中的一種。

非確定性有限狀態機

給定某個狀態，一個輸入可以導致多個不同的狀態。

圖 1：確定性有限狀態機。

在圖 1 中，狀態開始於狀態 1；給定輸入“X”，狀態變為狀態 2，或者給定輸入“Y”，狀態變為狀態 3。

圖 2：非確定性有限狀態機。

在圖 2 中，給定輸入“X”，狀態可以保持不變或變為狀態 2。

請注意，任何 正則表示式都可以由狀態機表示。