編譯器設計中的有限自動機是什麼？

自動機是數字計算機的一種抽象模型，具有離散的輸入和輸出。每個自動機都包含一個讀取輸入的機制。可以認為輸入是在給定字母表上的字串，寫在自動機可以讀取的輸入檔案上。輸入檔案被分成稱為單元格的較小部分。

它是一種語言的機器或識別器，用於檢查語言是否接受該字串。在**有限自動機**中，**有限**表示有限數量的狀態，而自動機表示在沒有人工干預的情況下工作的**自動**機器。有限自動機由一組有限狀態和從一個狀態到另一個狀態的轉換組成，這些轉換出現在從字母表 $\sum$ 中選擇的輸入符號上。

有限自動機的表示

有兩種方法可以表示有限自動機：

• 狀態轉換圖

它是一個具有狀態和邊的有向圖或流程圖。

示例

0, 1, 2→States 0 →Initial State 2→Final State a,b→Input Symbols

• 狀態轉換表

有限自動機可以用 5 元組 (Q,∑,$\delta$,q₀,F) 表示

• Q 是一個有限的非空狀態集。
• $\sum$ 是一個有限的輸入符號集。
• $\delta$ 是狀態轉換函式。
• q₀ ∈ Q 是初始狀態。
• F $\subseteq$ Q 是終結狀態集。

**示例** - 設計一個接受字串“abb”的有限自動機。

解決方案

狀態：Q= {q₀,q₁,q₂,q₃}

輸入符號：$\sum$ ={a,b}

狀態轉換函式 $\delta$: {$\delta$ (q₀,𝑎)=q₁,$\delta$(q₁,𝑏)=q₂,$\delta$(q₂,b)=q₃}

初始狀態：q₀

終結狀態 (F) : {q3}

有限自動機的型別

有限自動機有兩種型別，如下所示：

• 確定性有限自動機 (DFA)

“確定性”意味著對於每個輸入，自動機從其當前狀態轉換到下一個狀態只有一個狀態。

DFA 可以用 5 元組 (Q,$\sum$,$\delta$,q₀,F) 表示

• Q 是一個有限的非空狀態集。
• ∑ 是一個有限的輸入符號集。
• $\delta$ 是一個狀態轉換函式，用於從當前狀態移動到下一個狀態。

∴ $\delta$:Q x Σ → Q

• q₀ ∈ Q 是初始狀態。
• F $\subseteq$ Q 是終結狀態集。
• 非確定性有限自動機 (NFA)

“非確定性”意味著可能存在多個可能的轉換。因此，對於給定的輸入，輸出是非確定性的。

NFA 可以用 5 元組 (Q,$\sum$,$\delta$,q₀,F) 表示

• Q 是一個有限的非空狀態集。
• ∑ 是一個有限的輸入符號集。
• $\delta$ 是一個狀態轉換函式，用於從當前狀態移動到下一個狀態。

∴ $\delta$:Q x $\sum$ → 2^Q

• q₀ ∈ Q 是初始狀態。
• F $\subseteq$ Q 是終結狀態集。

Ginni

更新於： 2021年10月26日

4K+ 次檢視

啟動您的 職業生涯

透過完成課程獲得認證

開始