有限狀態機

有限狀態機

有限狀態機,(英語:Finite-state machine, FSM),又稱有限狀態自動機,簡稱狀態機,是表示有限個狀態以及在這些狀態之間的轉移和動作等行為的數學模型。

概念術語

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

進入動作(entry action):在進入狀態時進行

退出動作:在退出狀態時進行

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

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

下面展示最常見的表示:當前狀態(B)和條件(Y)的組合指示出下一個狀態(C)。完整的動作信息可以只使用腳註來增加。包括完整動作信息的 FSM 定義可以使用狀態表。

狀態轉移表
當前狀態 → 條件 ↓狀態 A狀態 B狀態 C
條件 X
條件 Y 狀態 C
條件 Z

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

地位

有限狀態機 有限狀態機

在數字電路系統中,有限狀態機是一種十分重要的時序邏輯電路模組

作用

它對數字系統的設計具有十分重要的作用。

有限狀態機是指輸出取決於過去輸入部分和當前輸入部分的時序邏輯電路。一般來說,除了輸入部分和輸出部分外,有限狀態機還含有一組具有“記憶”功能的暫存器,這些暫存器的功能是記憶有限狀態機的內部狀態,它們常被稱為狀態暫存器。在有限狀態機中,狀態暫存器的的下一個狀態不僅與輸入信號有關,而且還與該暫存器的當前狀態有關,因此有限狀態機又可以認為是組合邏輯和暫存器邏輯的一種組合。其中,暫存器邏輯的功能是存儲有限狀態機的內部狀態;而組合邏輯又可以分為次態邏輯和輸出邏輯兩部分,次態邏輯的功能是確定有限狀態機的下一個狀態,輸出邏輯的功能是確定有限狀態機的輸出。

分類

在實際的套用中,根據有限狀態機是否使用輸入信號,設計人員經常將其分為Moore型有限狀態機和Mealy型有限狀態機兩種類型。1 Moore型有限狀態機 其輸出信號僅與當前狀態有關,即可以把Moore型有限狀態的輸出看成是當前狀態的函式。2 Mealy型有限狀態機 其輸出信號不僅與當前狀態有關,而且還與所有的輸入信號有關,即可以把Mealy型有限狀態機的輸出看成是當前狀態和所有輸入信號的函式。

編程

有限狀態機體現了兩點:首先是離散的,然後是有限的。

State:

狀態這個詞有些難以定義,狀態存儲關於過去的信息,就是說它反映從系統開始到現在時刻的輸入變化。

Actions & Transitions:

轉換指示狀態變更,並且用必須滿足來確使轉移發生的條件來描述它。動作是在給定時刻要進行的活動的描述。

Guards:

檢測器出現的原因是為了檢測是否滿足從一個狀態切換到另外一個狀態的條件。

Event:

事件,又見事件,籠統說來,對系統重要的某件事情被稱為事件。

恩,就這些了,有些迷惑么:),恩,我們來理清一下思路:先從事件說起,事件是有生命

的,它經歷:

1).被產生(被接受,等待被處理,一般放入事件佇列)

2).被分發(從事件佇列取出,分發到回響的狀態機處理)

3).死亡(當狀態機處理了該事件,它隨之死亡)

從一個狀態切換到另外一個狀態被稱為狀態轉換,而引起它的事件稱為觸發事件.(可以看到,不是所有的事件都會引起狀態的轉換).

提到狀態轉換,不能不提及檢測器(Guards),只有當檢測器的值為TRUE時候,才能啟動轉換

套用

常見的計算機就是使用有限狀態機作為計算模型的:對於記憶體的不同狀態,CPU通過讀取記憶體值進行計算,更新記憶體中的狀態。CPU還通過訊息匯流排接受外部輸入設備(如鍵盤、滑鼠)的指令,計算後更改記憶體中的狀態,計算結果輸出到外部顯示設備(如顯示器),以及持久化存儲在硬碟。

電腦遊戲設計中也經常使用有限狀態機模型。以水果忍者遊戲為例,遊戲中水果的狀態是有限狀態,其運行軌跡是由模擬物理運動規律的計算公式運算而成的,一個香蕉拋起來後會按照拋物線運行,其每一幀位置變化都是一個狀態的改變,狀態改變通過計算公式來決定。當然作為遊戲不會僅僅這么簡單,如果這么簡單就是動畫了,遊戲還有複雜的人機互動事件,比如用手在螢幕上“切”了水果,水果感知到這個事件後,會按照程式邏輯進入爆炸狀態。

相關詞條

相關搜尋

熱門詞條

聯絡我們