什麼是有限自動機？

有限自動機是一種抽象的計算裝置。它是一個數學模型，具有離散的輸入、輸出、狀態和一組狀態轉換，這些轉換髮生在來自字母表Σ的輸入符號上。

有限自動機的表示

有限自動機可以用以下三種方式表示：

• 圖形化（狀態轉換圖）
• 表格化（狀態轉換表）
• 數學化（狀態轉換函式）

有限自動機的形式定義

有限自動機定義為一個五元組

M=(Q, Σ, δ,q0,F)

其中，

• Q：稱為狀態的有限集合。
• Σ：稱為字母表的有限集合。
• δ：Q × Σ → Q 是狀態轉換函式。
• q0 ∈ Q 是起始狀態或初始狀態。
• F：終止狀態或接受狀態。

有限自動機可以表示如下：

• 狀態轉換圖
• 狀態轉換表
• 狀態轉換函式

狀態轉換圖

它是一個有向圖，圖的頂點對應於有限自動機的狀態。

下面是一個狀態轉換圖的示例：

這裡，

• {0,1}：輸入
• q1：初始狀態
• q2：中間狀態
• qf：終止狀態

狀態轉換表

它基本上是狀態轉換函式的表格表示，該函式接受兩個引數（一個狀態和一個符號）並返回一個值（“下一個狀態”）。

δ : Q × Σ → Q

在狀態轉換表中，考慮以下因素：

• 行對應於狀態。
• 列對應於輸入符號。
• 條目對應於下一個狀態。
• 起始狀態用 -> 標記。
• 接受狀態用 * 標記。

狀態轉換表示例如下：

狀態轉換表如下：

狀態轉換函式

狀態轉換函式用 δ 表示。下面提到的兩個引數是傳遞給此狀態轉換函式的引數。

• 當前狀態
• 輸入符號

狀態轉換函式返回一個狀態，可以稱為下一個狀態。

δ (current_state, current_input_symbol) = next_state

例如，δ(q0,a)=q1

Bhanu Priya

更新於：2021年6月11日

15K+ 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習