有限狀態自動機

有限狀態自動機（FSM "finite state machine" 或者FSA "finite state automaton" ）,是為研究有限記憶體的計算過程和某些語言類而抽象出的一種計算模型。有限狀態自動機擁有有限數量的狀態，每個狀態可以遷移到零個或多個狀態，輸入字串決定執行哪個狀態的遷移。有限狀態自動機可以表示為一個有向圖。有限狀態自動機是自動機理論的研究對象。

有限狀態自動機定義

是具有離散輸入和輸出的系統的一種數學模型。

其主要特點有以下幾個方面：

– (1)系統具有有限個狀態，不同的狀態代表不同的意義。按照實際的需要，系統可以在不同的狀態下完成規定的任務。
– (2)我們可以將輸入字元串中出現的字元匯集在一起構成一個字母表。系統處理的所有字元串都是這個字母表上的字元串。
– (3)系統在任何一個狀態下，從輸入字元串中讀入一個字元，根據當前狀態和讀入的這個字元轉到新的狀態。
– (4)系統中有一個狀態，它是系統的開始狀態。
– (5)系統中還有一些狀態表示它到目前為止所讀入的字元構成的字元串是語言的一個句子。

形式定義

• 定義：有限狀態自動機(FA—finite automaton)是一個五元組：
– M=(Q, Σ, δ, q0, F)
• 其中，
– Q——狀態的非空有窮集合。∀q∈Q，q稱為M的一個狀態。
– Σ——輸入字母表。
– δ——狀態轉移函式，有時又叫作狀態轉換函式或者移動函式，δ：Q×Σ→Q，δ(q,a)=p。
– q0——M的開始狀態，也可叫作初始狀態或啟動狀態。q0∈Q。
– F——M的終止狀態集合。F被Q包含。任給q∈F，q稱為M的終止狀態。