有限狀態機

通過簡單的示例快速了解什麼是狀態機

有很多談論有限狀態機這些天在JavaScript領域。

有個受歡迎的圖書館叫做X狀態,最近在GitHub上有超過11000個星星,我最近遇到了這個話題,而且我還在Twitter和其他地方繼續閱讀有關它的信息。這是一個非常酷的項目。

20年前,我在高中時第一次遇到了有限狀態機和自動機,然後在大學的數字設計課程中又遇到了它們。

該數字設計課程涉及編碼信息,布爾代數,組合網絡,順序電路,順序狀態機,算術電路,VHDL等內容。

我發現應用於前端工程的有限狀態機這一主題非常令人驚訝,然後我回到舊書中,看看是否能找到對它們的很好的解釋。

我確實找到了很多信息,當然,作為教科書,事情變得比需要的更為複雜(恕我直言)。我想簡化事情,所以我決定為普通人寫一些解釋,而不是理論上的解釋或通過考試的任何解釋。您可以應用於現實世界的事物。

狀態機

在研究什麼是有限狀態機之前,我想先介紹一下狀態機。

世界充滿了狀態機。您到處都可以看到它們,但也許您沒有想到它們。閱讀完本教程後,我確定您會指出現實世界中的對像對您的朋友說:“那是狀態機”(取決於您朋友的書呆子水平)。

最受歡迎和最常見的示例是紅綠燈

在任何時間點,流量信號燈都具有定義的狀態。通常,它要么:

  • 綠燈亮,其他2燈滅
  • 呈紅色亮起,另兩個熄滅
  • 當黃燈點亮時,其他2燈熄滅

Traffic lights

(某些信號量略有不同,但出於本示例的考慮,我們不在乎)

在State Machines術語中,稱為開燈或關燈輸出

這三種情況中的每一種都被稱為狀態。交通信號燈在接收到輸入時將改變狀態,通常只是一個固定的計時器,該計時器決定交通信號燈應保持綠色,黃色和紅色的時間。

在這種情況下,計時器是輸入系統的。一些信號燈具有一個按鈕,行人可以按下該按鈕以使紅色顯示在汽車上,這將是另一個輸入。

在狀態機中,狀態只能改變(而我們有一個過渡)以響應輸入。

有限狀態機

據說我們的交通燈狀態機是有限因為我們有有限數量的州。

某些系統可能具有無限數量的狀態。

就像世界生態系統模型或昆蟲的生命一樣。我們不能在有限數量的狀態下定義它。

但是交通燈?這很簡單,它具有3個狀態,就像我們上面說的那樣。

我們可以使用更多的有限狀態機示例:

  • 自動販賣機
  • 地鐵入口旋轉門
  • 加熱系統
  • 自動化地鐵系統
  • 自動駕駛汽車系統
  • 一部電梯

但是,讓我們繼續使用我們的交通信號燈示例,該示例非常簡單,我們可以輕鬆地對此進行推理。

對狀態機建模

當然,交通信號燈並不是孤立存在的。這是另一種有限狀態機,對於交叉路口每條道路的每一側安裝的每個交通信號燈設備,它都包含多個不同的有限狀態機,這些設備會同步工作。

Crossroads

現在不要考慮。讓我們專注於1個單一的交通信號燈。

如上所述,我們有3個狀態,分別可以稱為綠色,紅色,黃色。

The 3 states

我們有一個初始狀態。假設當我們重置它們時,我們的交通燈會在green狀態。

Initial state

我們有一個計時器,在綠色狀態50秒後,將信號量移到yellow狀態。我們有8秒的時間yellow狀態,然後我們轉到red狀態,我們在那兒坐了32秒鐘,因為那條路是次要的,因此值得花更少的時間進行綠化。此後,信號量將恢復為綠色狀態,並且循環將無限期繼續,直到斷電並且信號量在再次獲得電源時重置為止。

總共,我們有一個90秒的周期。

這是我們可以建模的方式:

The model

我們也可以使用狀態轉換錶,其中顯示了狀態機器當前在哪裡,什麼是輸入它收到的是什麼下一個狀態輸出

狀態 輸入 下一個狀態 輸出
綠色的 計時器50秒 黃色的 綠燈亮,其他燈滅
黃色的 定時器8秒 紅色的 黃燈亮,其他燈滅
紅色的 計時器32秒 綠色的 紅燈亮,其他燈滅

在我們的簡單情況下,給定機器的任何狀態,我們只有一個邏輯狀態要去,所以我製作的表和圖表非常非常簡單。

但是,當您的系統開始變得更加複雜時,適當地放置此類圖表和分析將非常有幫助,因為與簡單地掌握所有內容相比,您可以更輕鬆地推斷出您的應用程序。

具有更複雜狀態轉換的有限狀態機

上面的例子很簡單。現在讓我們為另一個有限狀態機建模。

我們的現實世界場景是:我們有一所房子,有一個門,2個按鈕和3個燈。

在默認狀態下,所有指示燈均熄滅。

lights

進入房屋後,您可以按一下擁有的2個按鈕之一,p1或者p2。當您按下其中任何一個按鈕時,l1燈亮。

想像這是入口燈,您可以脫下外套。完成後,您可以決定要進入哪個房間(例如廚房或臥室)。

如果按下按鈕p1l1關閉並l2打開。相反,如果您按下按鈕p2l1關閉並l3打開。

再次按下2個按鈕中的任何一個,p1或者p2,當前亮起的燈將熄滅,我們將回到系統的初始狀態。

這個有限狀態機比第一個有限狀態機要復雜一些,因為這次我們可以根據輸入有多個路由。

讓我們對此建模。

我們基本上有4種狀態:

  • 沒有燈亮
  • l1打開
  • l2打開
  • l3打開

model lights

我們有2個輸入:

  • p1
  • p2

如果我們從初始狀態開始,並且嘗試根據隨時間推移觸發輸入的方式來建模可能發生的所有事情,那麼最終結果是:

State transitions

可以使用此表對其進行匯總:

狀態 輸入 下一個狀態
沒有燈亮 p1 l1打開
沒有燈亮 p2 l1打開
l1打開 p1 l2打開
l1打開 p2 l3打開
l2打開 p1 沒有燈亮
l2打開 p2 沒有燈亮
l3打開 p1 沒有燈亮
l3打開 p2 沒有燈亮

這是一個簡短的解釋,但也許會使事情“點擊”。


更多計算機教程: