快速概述狀態機,並提供簡單的例子。
最近在 JavaScript 領域中越來越多地談論 有限狀態機。
有一個名叫 XState 的流行庫,在 GitHub 上有超過 1.1 萬顆星星,我最近遇到了它,並且在 Twitter 和其他地方都看到它。這是一個非常酷的項目。
我第一次接觸有限狀態機和自動機是在 20 年前的高中時代,然後在大學的數位設計課程中又遇到。
這門數位設計課程主要涉及編碼信息、布林代數、組合電路、時序電路、序列狀態機、算術電路、VHDL 等內容。
我發現將有限狀態機應用於前端工程非常有趣,於是我回頭翻閱了以前的教科書,看看能否找到一個好的解釋。
我確實找到了很多資訊,但當然由於教科書的緣故,事情被複雜化得沒有必要(在我看來)。我喜歡簡化事物,因此我決定寫一個適合普通人的小節,並非理論的或任何為了通過考試而製作的東西。你可以應用於實際世界的事物。
狀態機
在介紹什麼是有限狀態機之前,我要先介紹什麼是狀態機。
世界上到處都是狀態機。你可以在各個地方看到它們,但也許你沒有把它們視為狀態機。在閱讀本教程之後,我相信你會指出現實世界中的一些物體,對你的朋友說:“這是一個 狀態機”(取決於你的朋友對於書呆子程度)。
最受歡迎且最常見的例子就是交通信號燈。
任何時候,交通信號機都有一個明確的狀態。通常,它要麼:
- 綠燈亮,其他兩個燈熄滅;
- 紅燈亮,其他兩個燈熄滅;
- 黃燈亮,其他兩個燈熄滅。
(有些交通信號燈可能有些區別,但對於本例子而言,我們不需要關心)
在狀態機的術語中,燈號的開啟或關閉被稱為輸出。
以上的三種情況被稱為狀態。當交通信號機接收到一個輸入時,通常只是一個固定的計時器,該計時器決定綠燈、黃燈和紅燈應該亮多久,信號機的狀態會更改。
在這種情況下,計時器是系統的輸入。有些信號機配有一個行人可以按下的按鈕,以導致紅燈顯示給汽車,這是另一個輸入。
在狀態機中,狀態只能在根據輸入的情況下更改(我們稱之為轉換)。
有限狀態機
我們的交通信號燈狀態機被稱為有限,因為我們只有有限的狀態。
有些系統可能有無限個狀態,例如世界生態系統模型或昆蟲的生活。我們無法用有限數量的狀態來定義它。
但是交通信號燈呢?這是一個簡單的東西,它只有三種狀態,如上所述。
我們還可以舉出許多例子:
- 自動售貨機
- 地鐵入口的轉閘
- 暖氣系統
- 自動地鐵系統
- 自動駕駛車系統
- 電梯
但讓我們先專注在我們的交通信號燈示例上,這是非常簡單的,我們可以很容易地理解。
建立狀態機模型
當然,交通信號機不是單獨存在的。這是另一個有限狀態機,其中每個十字路口的每一側道路上都被安裝了多個交通信號機,它們同步工作。
現在先不要考慮它。讓我們專注於一個單獨的交通信號機。
如前所述,我們有 3 種狀態,可以稱之為綠燈、紅燈、黃燈。
我們有一個初始狀態。假設在重置交通信號燈時,我們的信號燈處於 green
狀態。
我們有一個計時器,在綠燈狀態持續 50 秒後,信號機切換到 yellow
狀態。黃燈狀態持續 8 秒,然後切換到 red
狀態,並在那裡停留 32 秒,因為那條路是附屬的,應該給予較少時間。之後,信號機回到綠燈狀態,這個循環無限地繼續下去,直到電力被切斷,信號機重新接通電源時重置。
總計,我們有一個 90 秒的循環。
這是我們如何建立模型的:
我們也可以使用一個狀態轉換表來建立模型,該表顯示機器當前的狀態、收到的輸入、下一個狀態和輸出:
狀態 | 輸入 | 下一個狀態 | 輸出 |
---|---|---|---|
綠燈 | 計時器 50 秒 | 黃燈 | 綠燈亮,其他熄滅 |
黃燈 | 計時器 8 秒 | 紅燈 | 黃燈亮,其他熄滅 |
紅燈 | 計時器 32 秒 | 綠燈 | 紅燈亮,其他熄滅 |
在我們這個簡單的情況下,對於機器的任何狀態,我們只有一個可以前進的邏輯狀態,所以我這裡提供的表格和圖表非常簡單。
但當你的系統變得更加複雜時,擁有這樣的圖表和分析非常有幫助,因為你可以更容易地推理你的應用,而不僅僅是將所有事情放在腦海中。
具有更複雜狀態轉換的有限狀態機
上面的例子非常簡單。現在讓我們建立另一個有限狀態機。
我們的現實場景是這樣的:我們有一棟房子,裡面有一扇門,2個按鈕和 3 個燈。
在初始狀態下,燈都關掉了。
當你進入房子後,可以按下其中一個按鈕,p1
或 p2
。當你按下任何一個按鈕時,l1
燈會亮起。
想像這是入口燈,你可以脫下外套。一旦你完成,你就可以決定你想去哪個房間(比如廚房或臥室)。
如果你按下按鈕 p1
,l1
會熄滅,l2
會亮起。如果你按下按鈕 p2
,l1
會熄滅,l3
會亮起。
再次按下任何一個按鈕,p1
或 p2
,當前亮著的燈會熄滅,系統回到初始狀態。
這個有限狀態機比第一個稍微複雜一些,因為這次我們根據輸入可以有多條路徑。
讓我們來建模。
基本上我們有 4 種狀態:
- 沒有任何燈亮
l1
亮l2
亮l3
亮
我們有 2 個輸入:
p1
p2
如果我們從初始狀態開始,並嘗試在時間內根據輸入發生的情況建模一切,我們得到:
可以用以下表格總結:
狀態 | 輸入 | 下一個狀態 |
---|---|---|
沒有任何燈亮 | p1 按下 |
l1 亮 |
沒有任何燈亮 | p2 按下 |
l1 亮 |
l1 亮 |
p1 按下 |
l2 亮 |
l1 亮 |
p2 按下 |
l3 亮 |
l2 亮 |
p1 按下 |
沒有任何燈亮 |
l2 亮 |
p2 按下 |
沒有任何燈亮 |
l3 亮 |
p1 按下 |
沒有任何燈亮 |
l3 亮 |
p2 按下 |
沒有任何燈亮 |
這是一個簡短且簡單的解釋,但希望能有所啟發。