自動機理論 - 快速指南

---

---

自動機理論簡介

自動機 - 它是什麼？

"自動機"一詞源於希臘語 "αὐτόματα"，意為"自動"。自動機（複數為自動機）是一種抽象的自動推進計算裝置，它自動遵循預定的操作序列。

具有有限狀態數的自動機稱為有限自動機 (FA) 或有限狀態機 (FSM)。

有限自動機的形式化定義

自動機可以用一個 5 元組 (Q, ∑, δ, q₀, F) 表示，其中 -

• Q 是一個有限的狀態集。

• ∑ 是一個有限的符號集，稱為自動機的字母表。

• δ 是轉移函式。

• q₀ 是處理任何輸入的初始狀態 (q₀ ∈ Q)。

• F 是 Q 的一組終態/狀態 (F ⊆ Q)。

相關術語

字母表

• 定義 - 字母表是任何有限的符號集。

• 示例 - ∑ = {a, b, c, d} 是一個字母表集，其中 'a'、'b'、'c' 和 'd' 是符號。

字串

• 定義 - 字串是從 ∑ 中取出的符號的有限序列。

• 示例 - 'cabcad' 是字母表集 ∑ = {a, b, c, d} 上的一個有效字串

字串的長度

• 定義 - 字串中存在的符號數。(用|S|表示)。

• 示例 -

  • 如果 S = 'cabcad'，|S|= 6

  • 如果 |S|= 0，則稱為空字串（用λ或ε表示）

克萊尼星號

• 定義 - 克萊尼星號∑*是符號或字串集∑上的一個一元運算子，它給出∑上所有可能長度的所有可能字串的無限集，包括λ。

• 表示 - ∑* = ∑₀ ∪ ∑₁ ∪ ∑₂ ∪……. 其中 ∑_p 是長度為 p 的所有可能字串的集合。

• 示例 - 如果 ∑ = {a, b}，∑* = {λ, a, b, aa, ab, ba, bb,………..}

克萊尼閉包/加號

• 定義 - 集合∑⁺是∑上所有可能長度的所有可能字串的無限集，不包括λ。

• 表示 - ∑⁺ = ∑₁ ∪ ∑₂ ∪ ∑₃ ∪…….

  ∑⁺ = ∑* − { λ }

• 示例 - 如果 ∑ = { a, b } ，∑⁺ = { a, b, aa, ab, ba, bb,………..}

語言

• 定義 - 語言是某個字母表 ∑ 的 ∑* 的子集。它可以是有限的或無限的。

• 示例 - 如果語言取 ∑ = {a, b} 上長度為 2 的所有可能字串，則 L = { ab, aa, ba, bb }

確定性有限自動機

有限自動機可以分為兩種型別 -

• 確定性有限自動機 (DFA)
• 非確定性有限自動機 (NDFA / NFA)

確定性有限自動機 (DFA)

在 DFA 中，對於每個輸入符號，都可以確定機器將移動到的狀態。因此，它被稱為確定性自動機。由於它具有有限數量的狀態，因此該機器稱為確定性有限機或確定性有限自動機。

DFA 的形式化定義

DFA 可以用一個 5 元組 (Q, ∑, δ, q₀, F) 表示，其中 -

• Q 是一個有限的狀態集。

• ∑ 是一個有限的符號集，稱為字母表。

• δ 是轉移函式，其中 δ: Q × ∑ → Q

• q₀ 是處理任何輸入的初始狀態 (q₀ ∈ Q)。

• F 是 Q 的一組終態/狀態 (F ⊆ Q)。

DFA 的圖形表示

DFA 用稱為狀態圖的有向圖表示。

• 頂點表示狀態。
• 用輸入字母表標記的弧表示轉移。
• 初始狀態用一個空入射弧表示。
• 終態用雙圓表示。

示例

令一個確定性有限自動機為 →

• Q = {a, b, c},
• ∑ = {0, 1},
• q₀ = {a},
• F = {c}, 以及

轉移函式 δ 如以下表格所示 -

它的圖形表示如下所示 -

非確定性有限自動機

在 NDFA 中，對於特定的輸入符號，機器可以移動到機器中任何狀態的組合。換句話說，無法確定機器移動到的確切狀態。因此，它被稱為非確定性自動機。由於它具有有限數量的狀態，因此該機器稱為非確定性有限機或非確定性有限自動機。

NDFA 的形式化定義

NDFA 可以用一個 5 元組 (Q, ∑, δ, q₀, F) 表示，其中 -

• Q 是一個有限的狀態集。

• ∑ 是一個有限的符號集，稱為字母表。

• δ 是轉移函式，其中 δ: Q × ∑ → 2^Q

  （這裡取了 Q 的冪集 (2^Q)，因為在 NDFA 的情況下，從一個狀態可以轉移到 Q 狀態的任何組合）

• q₀ 是處理任何輸入的初始狀態 (q₀ ∈ Q)。

• F 是 Q 的一組終態/狀態 (F ⊆ Q)。

NDFA 的圖形表示：（與 DFA 相同）

NDFA 用稱為狀態圖的有向圖表示。

• 頂點表示狀態。
• 用輸入字母表標記的弧表示轉移。
• 初始狀態用一個空入射弧表示。
• 終態用雙圓表示。

示例

令一個非確定性有限自動機為 →

• Q = {a, b, c}
• ∑ = {0, 1}
• q₀ = {a}
• F = {c}

轉移函式 δ 如下所示 -

它的圖形表示如下所示 -

DFA 與 NDFA 的比較

下表列出了 DFA 和 NDFA 之間的區別。

接受器、分類器和轉換器

接受器（識別器）

計算布林函式的自動機稱為接受器。接受器的所有狀態要麼接受，要麼拒絕給它的輸入。

分類器

分類器具有兩個以上終態，並在終止時給出單個輸出。

轉換器

根據當前輸入和/或先前狀態產生輸出的自動機稱為轉換器。轉換器可以分為兩種型別 -

• 米利機 - 輸出取決於當前狀態和當前輸入。

• 穆爾機 - 輸出僅取決於當前狀態。

DFA 和 NDFA 的可接受性

當且僅當 DFA/NDFA 從初始狀態開始，在完全讀取字串後結束於接受狀態（任何終態）時，字串被 DFA/NDFA 接受。

字串 S 被 DFA/NDFA (Q, ∑, δ, q₀, F) 接受，當且僅當

δ*(q₀, S) ∈ F

DFA/NDFA 接受的語言L為

{S | S ∈ ∑* 且 δ*(q₀, S) ∈ F}

字串 S′ 未被 DFA/NDFA (Q, ∑, δ, q₀, F) 接受，當且僅當

δ*(q₀, S′) ∉ F

DFA/NDFA 未接受的語言 L′（接受語言 L 的補集）為

{S | S ∈ ∑* 且 δ*(q₀, S) ∉ F}

示例

讓我們考慮圖 1.3 中所示的 DFA。從 DFA 可以推匯出可接受的字串。

上述 DFA 接受的字串：{0, 00, 11, 010, 101, ...........}

上述 DFA 未接受的字串：{1, 011, 111, ........}

NDFA 到 DFA 的轉換

問題陳述

令X = (Q_x, ∑, δ_x, q₀, F_x)為一個接受語言 L(X) 的 NDFA。我們必須設計一個等價的 DFA Y = (Q_y, ∑, δ_y, q₀, F_y)，使得L(Y) = L(X)。以下過程將 NDFA 轉換為其等價的 DFA -

演算法

輸入 - 一個 NDFA

輸出 - 一個等價的 DFA

步驟 1 - 從給定的 NDFA 建立狀態表。

步驟 2 - 在等價 DFA 的可能輸入字母表下建立一個空白狀態表。

步驟 3 - 將 DFA 的起始狀態標記為 q0（與 NDFA 相同）。

步驟 4 - 找到每個可能輸入字母表的狀態組合 {Q₀, Q₁,... , Q_n}。

步驟 5 - 每次我們在輸入字母表列下生成一個新的 DFA 狀態時，我們都必須再次應用步驟 4，否則轉到步驟 6。

步驟 6 - 包含 NDFA 的任何終態的狀態是等價 DFA 的終態。

示例

讓我們考慮下圖所示的 NDFA。

使用上述演算法，我們可以找到其等價的DFA。DFA的狀態表如下所示。

DFA的狀態圖如下所示：

DFA最小化

使用Myhill-Nerode定理進行DFA最小化

演算法

輸入 - DFA

輸出 - 最小化的DFA

步驟1 - 為所有狀態對(Q_i, Q_j)（不一定直接連線）繪製表格 [最初所有均未標記]

步驟2 - 考慮DFA中每個狀態對(Q_i, Q_j)，其中Q_i ∈ F且Q_j ∉ F，反之亦然，並標記它們。[這裡F是終結狀態集]

步驟3 - 重複此步驟，直到我們無法再標記任何狀態 -

如果存在未標記的對(Q_i, Q_j)，則在對於某些輸入字母，對{δ (Q_i, A), δ (Q_i, A)}被標記時標記它。

步驟4 - 組合所有未標記的對(Q_i, Q_j)，並在簡化的DFA中將其設為單個狀態。

示例

讓我們使用演算法2來最小化下面顯示的DFA。

步驟1 - 我們為所有狀態對繪製表格。

步驟2 - 我們標記狀態對。

步驟3 - 我們將嘗試傳遞地標記狀態對，用綠色複選標記表示。如果我們將1輸入到狀態“a”和“f”，它將分別轉到狀態“c”和“f”。(c, f)已被標記，因此我們將標記對(a, f)。現在，我們將1輸入到狀態“b”和“f”；它將分別轉到狀態“d”和“f”。(d, f)已被標記，因此我們將標記對(b, f)。

步驟3之後，我們得到了未標記的狀態組合{a, b} {c, d} {c, e} {d, e}。

我們可以將{c, d} {c, e} {d, e}重新組合成{c, d, e}

因此，我們得到了兩個組合狀態：{a, b}和{c, d, e}

所以最終最小化的DFA將包含三個狀態{f}、{a, b}和{c, d, e}

使用等價定理進行DFA最小化

如果X和Y是DFA中的兩個狀態，如果它們不可區分，則可以將這兩個狀態組合成{X, Y}。如果至少存在一個字串S，使得δ (X, S)和δ (Y, S)中一個為接受狀態而另一個為非接受狀態，則這兩個狀態是可區分的。因此，當且僅當所有狀態都可區分時，DFA才是最小的。

演算法3

步驟1 - 所有狀態Q被分成兩個分割槽 - 終結狀態和非終結狀態，並表示為P₀。分割槽中的所有狀態都是0階等價的。取一個計數器k並將其初始化為0。

步驟2 - 將k加1。對於P_k中的每個分割槽，如果P_k中的狀態是k可區分的，則將它們分成兩個分割槽。如果存在一個輸入S，使得δ(X, S)和δ(Y, S)是(k-1)可區分的，則此分割槽中的兩個狀態X和Y是k可區分的。

步驟3 - 如果P_k ≠ P_k-1，則重複步驟2，否則轉到步驟4。

步驟4 - 組合k階等價集，並將它們設為簡化DFA的新狀態。

示例

讓我們考慮以下DFA：

讓我們將上述演算法應用於上述DFA：

• P₀ = {(c,d,e), (a,b,f)}
• P₁ = {(c,d,e), (a,b),(f)}
• P₂ = {(c,d,e), (a,b),(f)}

因此，P₁ = P₂。

簡化DFA中有三個狀態。簡化DFA如下：

Moore和Mealy機

有限自動機可能對每個轉換都有輸出。有兩種型別的有限狀態機生成輸出：

• Mealy機
• Moore機

Mealy機

Mealy機是一種FSM，其輸出取決於當前狀態以及當前輸入。

它可以用一個6元組(Q, ∑, O, δ, X, q₀)來描述，其中：

• Q 是一個有限的狀態集。

• ∑是一組有限的符號，稱為輸入字母表。

• O是一組有限的符號，稱為輸出字母表。

• δ是輸入轉移函式，其中δ: Q × ∑ → Q

• X是輸出轉移函式，其中X: Q × ∑ → O

• q₀ 是處理任何輸入的初始狀態 (q₀ ∈ Q)。

Mealy機的狀態表如下所示：

上述Mealy機的狀態圖如下：

Moore機

Moore機是一種FSM，其輸出僅取決於當前狀態。

Moore機可以用一個6元組(Q, ∑, O, δ, X, q₀)來描述，其中：

• Q 是一個有限的狀態集。

• ∑是一組有限的符號，稱為輸入字母表。

• O是一組有限的符號，稱為輸出字母表。

• δ是輸入轉移函式，其中δ: Q × ∑ → Q

• X是輸出轉移函式，其中X: Q → O

• q₀ 是處理任何輸入的初始狀態 (q₀ ∈ Q)。

Moore機的狀態表如下所示：

上述Moore機的狀態圖如下：

Mealy機與Moore機

下表突出顯示了區分Mealy機與Moore機的要點。

Moore機轉換為Mealy機

演算法4

輸入 - Moore機

輸出 - Mealy機

步驟1 - 獲取一個空白的Mealy機轉換表格式。

步驟2 - 將所有Moore機轉換狀態複製到此表格式中。

步驟3 - 檢查Moore機狀態表中的當前狀態及其相應的輸出；如果對於狀態Q_i輸出為m，則將其複製到Mealy機狀態表的輸出列中，無論Q_i出現在下一個狀態的何處。

示例

讓我們考慮以下Moore機：

現在我們應用演算法4將其轉換為Mealy機。

步驟1和2 -

步驟3 -

Mealy機轉換為Moore機

演算法5

輸入 - Mealy機

輸出 - Moore機

步驟1 - 計算Mealy機狀態表中每個狀態(Q_i)的不同的輸出數量。

步驟2 - 如果Q_i的所有輸出都相同，則複製狀態Q_i。如果它有n個不同的輸出，則將Q_i分解成n個狀態作為Q_in，其中n = 0, 1, 2.......

步驟3 - 如果初始狀態的輸出為1，則在開頭插入一個新的初始狀態，該狀態輸出0。

示例

讓我們考慮以下Mealy機：

這裡，狀態“a”和“d”分別僅輸出1和0，因此我們保留狀態“a”和“d”。但是狀態“b”和“c”產生不同的輸出（1和0）。因此，我們將b分成b₀, b₁，並將c分成c₀, c₁。

語法簡介

從文學意義上講，語法表示自然語言對話的句法規則。自英語、梵語、普通話等自然語言誕生以來，語言學家就試圖定義語法。

形式語言理論在計算機科學領域得到了廣泛的應用。Noam Chomsky在1956年提出了一個數學語法模型，該模型可用於編寫計算機語言。

語法

語法G可以正式地寫成一個4元組(N, T, S, P)，其中：

• N或V_N是一組變數或非終結符。

• T或∑是一組終結符。

• S是一個稱為起始符的特殊變數，S ∈ N

• P是終結符和非終結符的產生式規則。產生式規則的形式為α → β，其中α和β是V_N ∪ ∑上的字串，並且α至少有一個符號屬於V_N。

示例

語法G1 -

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

這裡，

• S、A和B是非終結符；

• a和b是終結符

• S是起始符，S ∈ N

• 產生式P : S → AB, A → a, B → b

示例

語法G2 -

(({S, A}, {a, b}, S,{S → aAb, aA → aaAb, A → ε } )

這裡，

• S和A是非終結符。

• a和b是終結符。

• ε是空字串。

• S是起始符，S ∈ N

• 產生式P : S → aAb, aA → aaAb, A → ε

來自語法的推導

可以使用語法中的產生式從其他字串推匯出字串。如果語法G有一個產生式α → β，我們可以說x α y在G中推匯出x β y。此推導寫為：

x α y ⇒G x β y

示例

讓我們考慮以下語法：

G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )

可以推匯出的某些字串為：

S ⇒ aAb 使用產生式S → aAb

⇒ aaAbb 使用產生式aA → aAb

⇒ aaaAbbb 使用產生式aA → aaAb

⇒ aaabbb 使用產生式A → ε

由文法生成的語言

可以從語法中推匯出的所有字串的集合稱為從該語法中生成的語言。由語法G生成的語言是正式定義的子集

L(G)={W|W ∈ ∑*, S ⇒G W}

如果L(G1) = L(G2)，則語法G1等價於語法G2。

示例

如果存在一個語法

G: N = {S, A, B} T = {a, b} P = {S → AB, A → a, B → b}

這裡S產生AB，我們可以用a替換A，用b替換B。這裡，唯一被接受的字串是ab，即

L(G) = {ab}

示例

假設我們有以下語法：

G: N = {S, A, B} T = {a, b} P = {S → AB, A → aA|a, B → bB|b}

這個語法生成的語言：

L(G) = {ab, a²b, ab², a²b², ………}

= {a^m bⁿ | m ≥ 1 且 n ≥ 1}

生成語言的語法的構造

我們將考慮一些語言，並將其轉換為產生這些語言的語法G。

示例

問題 - 假設，L (G) = {a^m bⁿ | m ≥ 0 且 n > 0}。我們必須找出產生L(G)的語法G。

解答

由於L(G) = {a^m bⁿ | m ≥ 0 且 n > 0}

被接受的字串集可以改寫為：

L(G) = {b, ab,bb, aab, abb, …….}

這裡，起始符號必須至少包含一個'b'，前面可以有任意數量的'a'，包括空。

為了接受字串集{b, ab, bb, aab, abb, …….}, 我們使用了以下產生式：

S → aS , S → B, B → b 和 B → bB

S → B → b (被接受)

S → B → bB → bb (被接受)

S → aS → aB → ab (被接受)

S → aS → aaS → aaB → aab(被接受)

S → aS → aB → abB → abb (被接受)

因此，我們可以證明L(G)中的每個字串都被產生式集生成的語言所接受。

因此語法：

G: ({S, A, B}, {a, b}, S, { S → aS | B , B → b | bB })

示例

問題 - 假設，L (G) = {a^m bⁿ | m > 0 且 n ≥ 0}。我們必須找出產生L(G)的語法G。

解答 -

由於L(G) = {a^m bⁿ | m > 0 且 n ≥ 0}，被接受的字串集可以改寫為：

L(G) = {a, aa, ab, aaa, aab ,abb, …….}

這裡，起始符號必須至少包含一個'a'，後面可以有任意數量的'b'，包括空。

為了接受字串集{a, aa, ab, aaa, aab, abb, …….}, 我們使用了以下產生式：

S → aA, A → aA , A → B, B → bB ,B → λ

S → aA → aB → aλ → a (被接受)

S → aA → aaA → aaB → aaλ → aa (被接受)

S → aA → aB → abB → abλ → ab (被接受)

S → aA → aaA → aaaA → aaaB → aaaλ → aaa (被接受)

S → aA → aaA → aaB → aabB → aabλ → aab (被接受)

S → aA → aB → abB → abbB → abbλ → abb (被接受)

因此，我們可以證明L(G)中的每個字串都被產生式集生成的語言所接受。

因此語法：

G: ({S, A, B}, {a, b}, S, {S → aA, A → aA | B, B → λ | bB })

喬姆斯基文法分類

根據諾姆·喬姆斯基，有四種類型的語法：0型、1型、2型和3型。下表顯示了它們之間的區別：

請檢視以下插圖。它顯示了每種語法型別的範圍：

3型語法

3型語法生成正則語言。3型語法必須在左側具有單個非終結符，並且右側由單個終結符或單個終結符後跟單個非終結符組成。

產生式必須採用以下形式X → a 或 X → aY

其中X, Y ∈ N (非終結符)

且a ∈ T (終結符)

如果S不出現在任何規則的右側，則允許規則S → ε。

示例

X → ε 
X → a | aY
Y → b 

2型語法

2型語法生成上下文無關語言。

產生式必須採用以下形式A → γ

其中 A ∈ N (非終結符)

且γ ∈ (T ∪ N)* (終結符和非終結符的字串)。

這些語法生成的語言可以被非確定性下推自動機識別。

示例

S → X a 
X → a 
X → aX 
X → abc 
X → ε

1型語法

1型語法生成上下文敏感語言。產生式必須採用以下形式

α A β → α γ β

其中A ∈ N (非終結符)

且α, β, γ ∈ (T ∪ N)* (終結符和非終結符的字串)

字串α和β可以為空，但γ不能為空。

如果S不出現在任何規則的右側，則允許規則S → ε。這些語法生成的語言可以被線性有界自動機識別。

示例

AB → AbBc 
A → bcA 
B → b 

0型語法

0型語法生成遞迴可列舉語言。產生式沒有限制。它們是任何短語結構語法，包括所有形式語法。

它們生成由圖靈機識別的語言。

產生式可以採用α → β的形式，其中α是終結符和非終結符的字串，至少包含一個非終結符，並且α不能為null。β是終結符和非終結符的字串。

示例

S → ACaB 
Bc → acB 
CB → DB 
aD → Db 

正則表示式

正則表示式可以遞迴定義如下：

• ε是一個正則表示式，表示包含空字串的語言。(L (ε) = {ε})

• φ是一個正則表示式，表示空語言。(L (φ) = { })

• x是一個正則表示式，其中L = {x}

• 如果X是一個表示語言L(X)的正則表示式，並且Y是一個表示語言L(Y)的正則表示式，則

  • X + Y是一個對應於語言L(X) ∪ L(Y)的正則表示式，其中L(X+Y) = L(X) ∪ L(Y)。

  • X . Y是一個對應於語言L(X) . L(Y)的正則表示式，其中L(X.Y) = L(X) . L(Y)

  • R*是一個對應於語言L(R*)的正則表示式，其中L(R*) = (L(R))*

• 如果我們從1到5多次應用任何規則，它們都是正則表示式。

一些RE示例

正則集

任何表示正則表示式值的集合都稱為正則集。

正則集的性質

性質1. 兩個正則集的並集是正則的。

證明 -

讓我們取兩個正則表示式

RE₁ = a(aa)* 和 RE₂ = (aa)*

因此，L₁ = {a, aaa, aaaaa,.....}（奇數長度的字串，不包括空）

且L₂ ={ ε, aa, aaaa, aaaaaa,.......}（偶數長度的字串，包括空）

L₁ ∪ L₂ = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,.......}

（所有可能長度的字串，包括空）

RE (L₁ ∪ L₂) = a* (它本身就是一個正則表示式)

因此，得證。

性質2. 兩個正則集的交集是正則的。

證明 -

讓我們取兩個正則表示式

RE₁ = a(a*) 和 RE₂ = (aa)*

因此，L₁ = { a,aa, aaa, aaaa, ....}（所有可能長度的字串，不包括空）

L₂ = { ε, aa, aaaa, aaaaaa,.......}（偶數長度的字串，包括空）

L₁ ∩ L₂ = { aa, aaaa, aaaaaa,.......}（偶數長度的字串，不包括空）

RE (L₁ ∩ L₂) = aa(aa)*，它本身就是一個正則表示式。

因此，得證。

性質3. 正則集的補集是正則的。

證明 -

讓我們取一個正則表示式：

RE = (aa)*

因此，L = {ε, aa, aaaa, aaaaaa, .......}（偶數長度的字串，包括空）

L的補集是不在L中的所有字串。

因此，L’ = {a, aaa, aaaaa, .....}（奇數長度的字串，不包括空）

RE (L’) = a(aa)*，它本身就是一個正則表示式。

因此，得證。

性質4. 兩個正則集的差集是正則的。

證明 -

讓我們取兩個正則表示式：

RE₁ = a (a*) 和 RE₂ = (aa)*

因此，L₁ = {a, aa, aaa, aaaa, ....}（所有可能長度的字串，不包括空）

L₂ = { ε, aa, aaaa, aaaaaa,.......}（偶數長度的字串，包括空）

L₁ – L₂ = {a, aaa, aaaaa, aaaaaaa, ....}

（所有奇數長度的字串，不包括空）

RE (L₁ – L₂) = a (aa)*，它是一個正則表示式。

因此，得證。

性質5. 正則集的反轉是正則的。

證明 -

我們必須證明如果L是一個正則集，則L^R也是正則的。

令，L = {01, 10, 11, 10}

RE (L) = 01 + 10 + 11 + 10

L^R = {10, 01, 11, 01}

RE (L^R) = 01 + 10 + 11 + 10，它是正則的

因此，得證。

性質6. 正則集的閉包是正則的。

證明 -

如果L = {a, aaa, aaaaa, .......} (奇數長度的字串，不包括空)

即， RE (L) = a (aa)*

L* = {a, aa, aaa, aaaa , aaaaa,……………} (所有長度的字串，不包括空)

RE (L*) = a (a)*

因此，得證。

性質7. 兩個正則集的連線是正則的。

證明 -

令 RE₁ = (0+1)*0 和 RE₂ = 01(0+1)*

這裡， L₁ = {0, 00, 10, 000, 010, ......} (以0結尾的字串集合)

並且 L₂ = {01, 010,011,.....} (以01開頭的字串集合)

那麼， L₁ L₂ = {001,0010,0011,0001,00010,00011,1001,10010,.............}

包含001作為子串的字串集合，可以用正則表示式表示為 -(0 + 1)*001(0 + 1)*

因此，得證。

正則表示式的恆等式

給定R、P、L、Q為正則表示式，以下恆等式成立：

• ∅* = ε
• ε* = ε
• RR* = R*R
• R*R* = R*
• (R*)* = R*
• RR* = R*R
• (PQ)*P =P(QP)*
• (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)*
• R + ∅ = ∅ + R = R (並集的恆等式)
• R ε = ε R = R (連線的恆等式)
• ∅ L = L ∅ = ∅ (連線的零元)
• R + R = R (冪等律)
• L (M + N) = LM + LN (左分配律)
• (M + N) L = ML + NL (右分配律)
• ε + RR* = ε + R*R = R*

Arden定理

為了找出有限自動機的正則表示式，我們使用Arden定理以及正則表示式的性質。

陳述 −

設P和Q為兩個正則表示式。

如果P不包含空字串，則R = Q + RP有一個唯一的解，即R = QP*

證明 -

R = Q + (Q + RP)P [代入R = Q + RP的值]

= Q + QP + RPP

當我們反覆遞迴地代入R的值時，得到以下等式：

R = Q + QP + QP² + QP³…..

R = Q (ε + P + P² + P³ + …. )

R = QP* [因為P*表示(ε + P + P2 + P3 + ….) ]

因此，得證。

應用Arden定理的假設

• 狀態轉換圖不能有空轉移
• 它必須只有一個初始狀態

方法

步驟1 − 為具有n個狀態和初始狀態q₁的DFA的所有狀態建立如下形式的方程。

q₁ = q₁R₁₁ + q₂R₂₁ + … + q_nR_n1 + ε

q₂ = q₁R₁₂ + q₂R₂₂ + … + q_nR_n2

…………………………

…………………………

…………………………

…………………………

q_n = q₁R_1n + q₂R_2n + … + q_nR_nn

R_ij表示從q_i到q_j的邊的標籤集，如果沒有這樣的邊存在，則R_ij = ∅

步驟2 − 求解這些方程以獲得最終狀態關於R_ij的方程

問題

構造一個與下面給定的自動機對應的正則表示式：

解答 −

這裡初始狀態和最終狀態是q₁。

三個狀態q1、q2和q3的方程如下：

q₁ = q₁a + q₃a + ε (ε轉移是因為q1是初始狀態)

q₂ = q₁b + q₂b + q₃b

q₃ = q₂a

現在，我們將求解這三個方程：

q₂ = q₁b + q₂b + q₃b

= q₁b + q₂b + (q₂a)b (代入q₃的值)

= q₁b + q₂(b + ab)

= q₁b (b + ab)* (應用Arden定理)

q₁ = q₁a + q₃a + ε

= q₁a + q₂aa + ε (代入q₃的值)

= q₁a + q₁b(b + ab*)aa + ε (代入q₂的值)

= q₁(a + b(b + ab)*aa) + ε

= ε (a+ b(b + ab)*aa)*

= (a + b(b + ab)*aa)*

因此，正則表示式為(a + b(b + ab)*aa)*。

問題

構造一個與下面給定的自動機對應的正則表示式：

解答 −

這裡初始狀態是q₁，最終狀態是q₂

現在我們寫下方程：

q₁ = q₁0 + ε

q₂ = q₁1 + q₂0

q₃ = q₂1 + q₃0 + q₃1

現在，我們將求解這三個方程：

q₁ = ε0* [因為，εR = R]

所以，q₁ = 0*

q₂ = 0*1 + q₂0

所以，q₂ = 0*1(0)* [根據Arden定理]

因此，正則表示式為0*10*。

從RE構造FA

我們可以使用Thompson構造法從正則表示式中找出有限自動機。我們將正則表示式簡化為最小的正則表示式，並將這些表示式轉換為NFA，最後轉換為DFA。

一些基本的RA表示式如下：

情況1 − 對於正則表示式“a”，我們可以構造以下FA：

情況2 − 對於正則表示式“ab”，我們可以構造以下FA：

情況3 − 對於正則表示式(a+b)，我們可以構造以下FA：

情況4 − 對於正則表示式(a+b)*，我們可以構造以下FA：

方法

步驟1 從給定的正則表示式構造一個帶空轉移的NFA。

步驟2 從NFA中移除空轉移，並將其轉換為等價的DFA。

問題

將以下RA轉換為其等價的DFA：1 (0 + 1)* 0

解答

我們將連線三個表示式“1”、“(0 + 1)*”和“0”

現在我們將移除ε轉移。在從NDFA中移除ε轉移後，我們得到以下結果：

這是一個與RE：1 (0 + 1)* 0對應的NDFA。如果你想將其轉換為DFA，只需應用第1章中討論的將NDFA轉換為DFA的方法。

帶空轉移的有限自動機 (NFA-ε)

帶空轉移的有限自動機(FA-ε)不僅在給出字母集的輸入後進行轉移，而且在沒有任何輸入符號的情況下進行轉移。這種無輸入的轉移稱為空轉移。

NFA-ε用一個5元組(Q, ∑, δ, q₀, F)正式表示，它由以下部分組成

• Q − 一組有限的狀態

• ∑ − 一組有限的輸入符號

• δ − 一個轉移函式δ : Q × (∑ ∪ {ε}) → 2^Q

• q₀ − 一個初始狀態q₀ ∈ Q

• F − 一組最終狀態/狀態Q (F⊆Q)。

上述(FA-ε)接受一個字串集：{0, 1, 01}

從有限自動機中移除空轉移

如果在一個NDFA中，在頂點X到頂點Y之間存在ϵ-轉移，我們可以使用以下步驟將其移除：

• 找到從Y出發的所有外向邊。
• 複製所有這些從X開始的邊，而不更改邊標籤。
• 如果X是初始狀態，則使Y也成為初始狀態。
• 如果Y是最終狀態，則使X也成為最終狀態。

問題

將以下NFA-ε轉換為沒有空轉移的NFA。

解答

步驟1 −

這裡ε轉移在q₁和q₂之間，所以設q₁為X，q_f為Y。

這裡從q_f出發的外向邊是對於輸入0和1到q_f。

步驟2 −

現在我們將複製所有這些從q₁出發的邊，而不更改從q_f出發的邊，並得到以下FA：

步驟3 -

這裡q₁是初始狀態，所以我們也使q_f成為初始狀態。

所以FA變為：

步驟4 −

這裡q_f是最終狀態，所以我們也使q₁成為最終狀態。

所以FA變為：

正則文法的泵引理

定理

設L是一個正則語言。那麼存在一個常數‘c’，使得對於L中的每個字串w：

|w| ≥ c

我們可以將w分解成三個字串，w = xyz，使得：

• |y| > 0
• |xy| ≤ c
• 對於所有k ≥ 0，字串xy^kz也在L中。

泵引理的應用

泵引理用於證明某些語言不是正則語言。它永遠不應該用於證明一個語言是正則語言。

• 如果L是正則的，則它滿足泵引理。

• 如果L不滿足泵引理，則它是非正則的。

證明語言L不是正則語言的方法

• 首先，我們必須假設L是正則的。

• 所以，泵引理應該對L成立。

• 使用泵引理得到一個矛盾：

  • 選擇w使得|w| ≥ c

  • 選擇y使得|y| ≥ 1

  • 選擇x使得|xy| ≤ c

  • 將剩餘的字串賦給z.

  • 選擇k使得生成的字串不在L中。

因此L不是正則的。

問題

證明L = {aⁱbⁱ | i ≥ 0}不是正則的。

解答 -

• 首先，我們假設L是正則的，n是狀態數。

• 設w = aⁿbⁿ。因此|w| = 2n ≥ n。

• 根據泵引理，設w = xyz，其中|xy| ≤ n。

• 設x = a^p，y = a^q，z = a^rbⁿ，其中p + q + r = n，p ≠ 0，q ≠ 0，r ≠ 0。因此|y| ≠ 0。

• 設k = 2。則xy²z = a^pa^2qa^rbⁿ。

• a的數量 = (p + 2q + r) = (p + q + r) + q = n + q

• 因此，xy²z = a^n+q bⁿ。由於q ≠ 0，xy²z不是aⁿbⁿ的形式。

• 因此，xy²z不在L中。因此L不是正則的。

DFA補集

如果(Q, ∑, δ, q₀, F)是一個接受語言L的DFA，則DFA的補集可以透過交換其接受狀態和非接受狀態來獲得，反之亦然。

我們將以一個例子來闡述這一點：

這個DFA接受語言

L = {a, aa, aaa , ............. }

在字母表上

∑ = {a, b}

所以，RE = a⁺。

現在我們將它的接受狀態與它的非接受狀態互換，反之亦然，並將得到以下結果：

這個DFA接受語言

Ľ = {ε, b, ab ,bb,ba, ............... }

在字母表上

∑ = {a, b}

注意 - 如果我們想對NFA取補集，我們必須先將其轉換為DFA，然後像以前的方法一樣交換狀態。

上下文無關文法簡介

定義 - 上下文無關文法（CFG）由一組有限的語法規則組成，是一個四元組(N, T, P, S)，其中

• N是非終結符的集合。

• T是終結符的集合，其中N ∩ T = NULL.

• P是一組規則，P: N → (N ∪ T)*，即產生式規則P的左側沒有任何右上下文或左上下文。

• S是起始符。

示例

• 文法({A}, {a, b, c}, P, A)，P : A → aA, A → abc。
• 文法({S, a, b}, {a, b}, P, S)，P: S → aSa, S → bSb, S → ε
• 文法({S, F}, {0, 1}, P, S)，P: S → 00S | 11F, F → 00F | ε

推導樹的生成

推導樹或語法樹是一個有序的根樹，它以圖形方式表示從上下文無關文法推匯出的字串的語義資訊。

表示技術

• 根節點 - 必須用起始符標記。

• 節點 - 用非終結符標記。

• 葉子節點 - 用終結符或ε標記。

如果S → x₁x₂ …… x_n是CFG中的一個產生式規則，則語法樹/推導樹如下：

有兩種不同的方法來繪製推導樹：

自頂向下方法 -

• 從起始符S開始

• 使用產生式向下到樹的葉子節點

自底向上方法 -

• 從樹的葉子節點開始

• 向上到根節點，即起始符S

樹的推導或結果

語法樹的推導或結果是從左到右連線樹的葉子節點的標籤而獲得的最終字串，忽略空值。但是，如果所有葉子節點都是空值，則推導結果為空值。

示例

設CFG {N,T,P,S}為

N = {S}, T = {a, b}, 起始符 = S, P = S → SS | aSb | ε

從上面CFG的一個推導是“abaabb”

S → SS → aSbS → abS → abaSb → abaaSbb → abaabb

句子形式和部分推導樹

部分推導樹是推導樹/語法樹的子樹，使得它的所有子節點都在子樹中或都不在子樹中。

示例

如果在任何CFG中，產生式為：

S → AB, A → aaA | ε, B → Bb| ε

部分推導樹可以是以下：

如果部分推導樹包含根節點S，則稱為句子形式。上面的子樹也處於句子形式。

字串的最左推導和最右推導

• 最左推導 - 最左推導是透過在每一步都應用最左邊的變數的產生式得到的。

• 最右推導 - 最右推導是透過在每一步都應用最右邊的變數的產生式得到的。

示例

設CFG中任意一組產生式規則為

X → X+X | X*X |X| a

在字母表{a}上。

字串"a+a*a"的最左推導可能是：

X → X+X → a+X → a + X*X → a+a*X → a+a*a

上面字串的分步推導如下所示：

上面字串"a+a*a"的最右推導可能是：

X → X*X → X*a → X+X*a → X+a*a → a+a*a

上面字串的分步推導如下所示：

左遞迴和右遞迴文法

在上下文無關文法G中，如果存在形式為X → Xa的產生式，其中X是非終結符，‘a’是終結符的字串，則稱為左遞迴產生式。具有左遞迴產生式的文法稱為左遞迴文法。

如果在上下文無關文法G中，如果存在形式為X → aX的產生式，其中X是非終結符，‘a’是終結符的字串，則稱為右遞迴產生式。具有右遞迴產生式的文法稱為右遞迴文法。

上下文無關文法中的二義性

如果上下文無關文法G對於某個字串w ∈ L(G)有多個推導樹，則稱為二義文法。對於從該文法生成的某個字串，存在多個最右推導或最左推導。

問題

檢查具有以下產生式規則的文法G：

X → X+X | X*X |X| a

是否二義的。

解答

讓我們找出字串"a+a*a"的推導樹。它有兩個最左推導。

推導1 - X → X+X → a +X → a+ X*X → a+a*X → a+a*a

語法樹1 -

推導2 - X → X*X → X+X*X → a+ X*X → a+a*X → a+a*a

語法樹2 -

由於單個字串"a+a*a"有兩個語法樹，因此文法G是二義的。

CFL閉包性質

上下文無關語言在以下方面是閉合的：

• 並集
• 連線
• Kleene星號運算

並集

設L₁和L₂是兩個上下文無關語言。則L₁ ∪ L₂也是上下文無關的。

示例

設L₁ = { aⁿbⁿ , n > 0}。相應的文法G₁將具有P: S1 → aAb|ab

設L₂ = { c^md^m , m ≥ 0}。相應的文法G₂將具有P: S2 → cBb| ε

L₁和L₂的並集，L = L₁ ∪ L₂ = { aⁿbⁿ } ∪ { c^md^m }

相應的文法G將具有額外的產生式S → S1 | S2

連線

如果L₁和L₂是上下文無關語言，則L₁L₂也是上下文無關的。

示例

語言L₁和L₂的並集，L = L₁L₂ = { aⁿbⁿc^md^m }

相應的文法G將具有額外的產生式S → S1 S2

克萊尼星號

如果L是上下文無關語言，則L*也是上下文無關的。

示例

設L = { aⁿbⁿ , n ≥ 0}。相應的文法G將具有P: S → aAb| ε

Kleene星號L₁ = { aⁿbⁿ }*

相應的文法G₁將具有額外的產生式S1 → SS₁ | ε

上下文無關語言在以下方面不是閉合的：

• 交集 - 如果L1和L2是上下文無關語言，則L1 ∩ L2不一定上下文無關。

• 與正則語言的交集 - 如果L1是正則語言，L2是上下文無關語言，則L1 ∩ L2是上下文無關語言。

• 補集 - 如果L1是上下文無關語言，則L1’可能不是上下文無關的。

CFG簡化

在CFG中，可能發生並非所有產生式規則和符號都需要用於字串的推導。此外，可能存在一些空產生式和單元產生式。消除這些產生式和符號稱為CFG的簡化。簡化基本上包括以下步驟：

• CFG的歸約
• 刪除單元產生式
• 刪除空產生式

CFG的歸約

CFG分為兩個階段歸約：

階段1 - 從CFG G匯出等價的文法G’，使得每個變數都推匯出某個終結符字串。

推導過程 -

步驟1 - 包括所有推匯出某個終結符的符號W₁，並初始化i=1。

步驟2 - 包括所有推匯出W_i的符號W_i+1。

步驟3 - 增加i並重復步驟2，直到W_i+1 = W_i。

步驟4 - 包括所有包含W_i的產生式規則。

階段2 - 從CFG G’匯出等價的文法G”，使得每個符號都出現在句子形式中。

推導過程 -

步驟1 - 將起始符包含在Y₁中，並初始化i = 1。

步驟2 - 包括所有可以從Y_i推匯出的符號Y_i+1，幷包括所有已應用的產生式規則。

步驟3 - 增加i並重復步驟2，直到Y_i+1 = Y_i。

問題

找到等價於文法G的歸約文法，該文法具有產生式規則P: S → AC | B, A → a, C → c | BC, E → aA | e

解答

階段1 -

T = { a, c, e }

W₁ = { A, C, E } 來自規則A → a, C → c和E → aA

W₂ = { A, C, E } U { S } 來自規則S → AC

W₃ = { A, C, E, S } U ∅

由於W₂ = W₃，我們可以匯出G’為：

G’ = { { A, C, E, S }, { a, c, e }, P, {S}}

其中P: S → AC, A → a, C → c , E → aA | e

階段2 -

Y₁ = { S }

Y₂ = { S, A, C } 來自規則S → AC

Y₃ = { S, A, C, a, c } 來自規則A → a和C → c

Y₄ = { S, A, C, a, c }

由於Y₃ = Y₄，我們可以匯出G”為：

G” = { { A, C, S }, { a, c }, P, {S}}

其中P: S → AC, A → a, C → c

刪除單元產生式

任何形式為A → B的產生式規則，其中A, B ∈ 非終結符，稱為單元產生式。

刪除過程 -

步驟1 - 要刪除A → B，每當B → x出現在文法中時，將產生式A → x新增到文法規則中。[x ∈ 終結符，x可以為空值]

步驟2 - 從文法中刪除A → B。

步驟3 - 從步驟1重複，直到所有單元產生式都被刪除。

問題

從以下內容中刪除單元產生式：

S → XY, X → a, Y → Z | b, Z → M, M → N, N → a

解答 −

文法中有3個單元產生式：

Y → Z, Z → M, 和 M → N

首先，我們將刪除M → N。

由於N → a，我們新增M → a，並刪除M → N。

產生式集變為

S → XY, X → a, Y → Z | b, Z → M, M → a, N → a

現在我們將刪除Z → M。

由於M → a，我們新增Z→ a，並刪除Z → M。

產生式集變為

S → XY, X → a, Y → Z | b, Z → a, M → a, N → a

現在我們將刪除Y → Z。

由於Z → a，我們新增Y→ a，並刪除Y → Z。

產生式集變為

S → XY, X → a, Y → a | b, Z → a, M → a, N → a

現在Z、M和N不可達，因此我們可以刪除它們。

最終的CFG是無單元產生式的：

S → XY, X → a, Y → a | b

刪除空產生式

在CFG中，如果存在產生式A → ε或存在從A開始並最終以ε結束的推導，則非終結符‘A’是可空變數

ε: A → .......… → ε

刪除過程

步驟1 - 找出推匯出ε的可空非終結符變數。

步驟2 - 對於每個產生式A → a，構造所有產生式A → x，其中x是從‘a’中刪除步驟1中的一個或多個非終結符得到的。

步驟3 - 將原始產生式與步驟2的結果合併，並刪除ε - 產生式。

問題

從以下內容中刪除空產生式：

S → ASA | aB | b, A → B, B → b | ∈

解答 −

有兩個可空變數：A和B

首先，我們將刪除B → ε。

移除B → ε後，產生式集合變為−

S→ASA | aB | b | a, A ε B| b | &epsilon, B → b

現在我們將移除A → ε。

移除A → ε後，產生式集合變為−

S→ASA | aB | b | a | SA | AS | S, A → B| b, B → b

這是最終沒有空轉移的產生式集合。

喬姆斯基正規化

如果產生式具有以下形式，則CFG處於喬姆斯基正規化−

• A → a
• A → BC
• S → ε

其中A、B和C是非終結符，而a是終結符。

轉換為喬姆斯基正規化的演算法−

步驟1 − 如果起始符號S出現在某個右部，則建立一個新的起始符號S’和一個新的產生式S’→ S。

步驟2 − 移除空產生式。（使用前面討論的空產生式移除演算法）

步驟3 − 移除單元產生式。（使用前面討論的單元產生式移除演算法）

步驟4 − 將每個產生式A → B₁…B_n（其中n > 2）替換為A → B₁C，其中C → B₂ …B_n。對右部有兩個或多個符號的所有產生式重複此步驟。

步驟5 − 如果任何產生式的右部形式為A → aB（其中a是終結符，A, B是非終結符），則將產生式替換為A → XB和X → a。對所有形式為A → aB的產生式重複此步驟。

問題

將以下CFG轉換為CNF

S → ASA | aB, A → B | S, B → b | ε

解答

(1) 由於S出現在右部，因此我們新增一個新狀態S₀，並將S₀→S新增到產生式集合中，它變為−

S₀→S, S→ ASA | aB, A → B | S, B → b | ∈

(2) 現在我們將移除空產生式−

B → ∈ 和 A → ∈

移除B → ε後，產生式集合變為−

S₀→S, S→ ASA | aB | a, A → B | S | ∈, B → b

移除A → ∈後，產生式集合變為−

S₀→S, S→ ASA | aB | a | AS | SA | S, A → B | S, B → b

(3) 現在我們將移除單元產生式。

移除S → S後，產生式集合變為−

S₀→S, S→ ASA | aB | a | AS | SA, A → B | S, B → b

移除S₀→ S後，產生式集合變為−

S₀→ ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

A → B | S, B → b

移除A→ B後，產生式集合變為−

S₀ → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

A → S | b

B → b

移除A→ S後，產生式集合變為−

S₀ → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

A → b |ASA | aB | a | AS | SA, B → b

(4) 現在我們將找出右部超過兩個變數的產生式

這裡，S₀→ ASA，S → ASA，A→ ASA違反了右部有兩個以上非終結符的規則。

因此，我們將應用步驟4和步驟5以獲得以下最終產生式集合，該集合處於CNF−

S₀→ AX | aB | a | AS | SA

S→ AX | aB | a | AS | SA

A → b |AX | aB | a | AS | SA

B → b

X → SA

(5) 我們必須更改產生式S₀→ aB，S→ aB，A→ aB

最終產生式集合變為−

S₀→ AX | YB | a | AS | SA

S→ AX | YB | a | AS | SA

A → b A → b |AX | YB | a | AS | SA

B → b

X → SA

Y → a

格雷巴赫正規化

如果產生式具有以下形式，則CFG處於格雷巴赫正規化−

A → b

A → bD₁…D_n

S → ε

其中A、D₁,....,D_n是非終結符，b是終結符。

將CFG轉換為格雷巴赫正規化的演算法

步驟1 − 如果起始符號S出現在某個右部，則建立一個新的起始符號S’和一個新的產生式S’ → S。

步驟2 − 移除空產生式。（使用前面討論的空產生式移除演算法）

步驟3 − 移除單元產生式。（使用前面討論的單元產生式移除演算法）

步驟4 − 移除所有直接和間接左遞迴。

步驟5 − 對產生式進行適當的替換以將其轉換為GNF的正確形式。

問題

將以下CFG轉換為CNF

S → XY | Xn | p

X → mX | m

Y → Xn | o

解答

這裡，S沒有出現在任何產生式的右部，並且產生式規則集中沒有單元或空產生式。因此，我們可以跳過步驟1到步驟3。

步驟4

現在替換

S → XY | Xo | p中的X

為

mX | m

我們得到

S → mXY | mY | mXo | mo | p。

並且替換

Y → X_n | o中的X

為

X → mX | m

我們得到

Y → mXn | mn | o的右部。

將兩個新產生式O → o和P → p新增到產生式集合中，然後我們得到以下最終GNF−

S → mXY | mY | mXC | mC | p

X → mX | m

Y → mXD | mD | o

O → o

P → p

CFG的泵引理

引理

如果L是一個上下文無關語言，則存在一個泵長度p，使得長度≥ p的任何字串w ∈ L可以寫成w = uvxyz，其中vy ≠ ε，|vxy| ≤ p，並且對於所有i ≥ 0, uvⁱxyⁱz ∈ L。

泵引理的應用

泵引理用於檢查語法是否為上下文無關。讓我們舉一個例子並展示如何進行檢查。

問題

找出語言L = {xⁿyⁿzⁿ | n ≥ 1}是否為上下文無關語言。

解答

假設L是上下文無關語言。那麼，L必須滿足泵引理。

首先，選擇泵引理中的一個數字n。然後，將z設為0ⁿ1ⁿ2ⁿ。

將z分解為uvwxy，其中

|vwx| ≤ n 且 vx ≠ ε。

因此，vwx不能同時包含0和2，因為最後一個0和第一個2至少相隔(n+1)個位置。有兩種情況−

情況1 − vwx沒有2。那麼vx僅包含0和1。那麼uwy（必須在L中）有n個2，但少於n個0或1。

情況2 − vwx沒有0。

這裡出現了矛盾。

因此，L不是上下文無關語言。

下推自動機簡介

PDA的基本結構

下推自動機是一種以類似於我們為正則語法設計DFA的方式實現上下文無關語法的方法。DFA可以記住有限量的資訊，但PDA可以記住無限量的資訊。

基本上，下推自動機是−

"有限狀態機" + "一個棧"

下推自動機具有三個元件−

• 輸入帶，
• 控制單元，以及
• 一個大小無限的棧。

棧指標掃描棧頂符號。

棧執行兩個操作−

• 壓棧 − 在頂部新增一個新符號。

• 出棧 − 讀取並移除頂部符號。

PDA可能讀取也可能不讀取輸入符號，但它必須在每次轉換中讀取棧頂。

PDA可以正式描述為一個7元組(Q, ∑, S, δ, q₀, I, F) −

• Q是有限數量的狀態

• ∑是輸入字母表

• S是棧符號

• δ是轉換函式：Q × (∑ ∪ {ε}) × S × Q × S*

• q₀是初始狀態(q₀ ∈ Q)

• I是初始棧頂符號(I ∈ S)

• F是接受狀態集(F ∈ Q)

下圖顯示了PDA中從狀態q₁到狀態q₂的轉換，標記為a,b → c −

這意味著在狀態q₁，如果我們遇到輸入字串‘a’並且棧頂符號是‘b’，那麼我們將‘b’出棧，將‘c’壓入棧頂，並移動到狀態q₂。

與PDA相關的術語

瞬時描述

PDA的瞬時描述(ID)由三元組(q, w, s)表示，其中

• q是狀態

• w是未消耗的輸入

• s是棧內容

轉向式符號

"轉向式"符號用於連線表示PDA的一次或多次移動的ID對。轉換過程由轉向式符號"⊢"表示。

考慮一個PDA (Q, ∑, S, δ, q₀, I, F)。轉換可以用以下轉向式符號數學表示−

(p, aw, Tβ) ⊢ (q, w, αb)

這意味著在從狀態p到狀態q進行轉換時，輸入符號‘a’被消耗，並且棧頂‘T’被新的字串‘α’替換。

注意 − 如果我們想要PDA的零次或多次移動，則必須使用符號(⊢*)來表示。

下推自動機的接受

有兩種不同的方法來定義PDA的可接受性。

終態可接受性

在終態可接受性中，當PDA讀取完整個字串後處於終態時，PDA接受該字串。從起始狀態，我們可以進行導致最終狀態的移動，並且棧中的值可以是任意值。只要我們最終處於終態，棧中的值就不相關。

對於PDA (Q, ∑, S, δ, q₀, I, F)，由終態集F接受的語言為−

L(PDA) = {w | (q₀, w, I) ⊢* (q, ε, x), q ∈ F}

對於任何輸入棧字串x。

空棧可接受性

在這裡，當PDA讀取完整個字串後，棧為空時，PDA接受該字串。

對於PDA (Q, ∑, S, δ, q₀, I, F)，由空棧接受的語言為−

L(PDA) = {w | (q₀, w, I) ⊢* (q, ε, ε), q ∈ Q}

示例

構造一個接受L = {0ⁿ 1ⁿ | n ≥ 0}的PDA

解答

此語言接受L = {ε, 01, 0011, 000111, ............................. }

在這裡，在這個例子中，‘a’和‘b’的數量必須相同。

• 最初，我們將一個特殊符號‘$’放入空棧中。

• 然後在狀態q₂，如果我們遇到輸入0並且棧頂為空，我們將0壓入棧中。這可能會迭代。如果我們遇到輸入1並且棧頂是0，我們將此0出棧。

• 然後在狀態q₃，如果我們遇到輸入1並且棧頂是0，我們將此0出棧。這也會迭代。如果我們遇到輸入1並且棧頂是0，我們將出棧棧頂元素。

• 如果在棧頂遇到特殊符號‘$’，則將其出棧，並最終進入接受狀態q₄。

示例

構造一個接受L = { ww^R | w = (a+b)* }的PDA

解答

最初，我們將一個特殊符號‘$’放入空棧中。在狀態q₂，正在讀取w。在狀態q₃，當每個0或1與輸入匹配時，將其出棧。如果給出任何其他輸入，PDA將進入死狀態。當我們到達特殊符號‘$’時，我們將進入接受狀態q₄。

PDA和上下文無關文法

如果一個文法G是上下文無關的，我們可以構建一個等價的非確定性PDA，該PDA接受由上下文無關文法G產生的語言。可以為文法G構建一個解析器。

此外，如果P是一個下推自動機，則可以構造一個等價的上下文無關文法G，其中

L(G) = L(P)

在接下來的兩個主題中，我們將討論如何將PDA轉換為CFG，反之亦然。

找到對應於給定CFG的PDA的演算法

輸入 − 一個CFG，G = (V, T, P, S)

輸出 − 等價的PDA，P = (Q, ∑, S, δ, q₀, I, F)

步驟1 − 將CFG的產生式轉換為GNF。

步驟2 − PDA只有一個狀態{q}。

步驟3 − CFG的起始符號將是PDA中的起始符號。

步驟4 − CFG的所有非終結符將是PDA的棧符號，CFG的所有終結符將是PDA的輸入符號。

步驟5 − 對於每個形如A → aX的產生式，其中a是終結符，A, X是非終結符和終結符的組合，建立一個轉移δ (q, a, A)。

問題

從以下CFG構建一個PDA。

G = ({S, X}, {a, b}, P, S)

其中產生式為−

S → XS | ε , A → aXb | Ab | ab

解答

令等價的PDA為，

P = ({q}, {a, b}, {a, b, X, S}, δ, q, S)

其中δ −

δ(q, ε , S) = {(q, XS), (q, ε )}

δ(q, ε , X) = {(q, aXb), (q, Xb), (q, ab)}

δ(q, a, a) = {(q, ε )}

δ(q, 1, 1) = {(q, ε )}

找到對應於給定PDA的CFG的演算法

輸入 − 一個CFG，G = (V, T, P, S)

輸出 − 等價的PDA，P = (Q, ∑, S, δ, q₀, I, F)，使得語法G的非終結符為{X_wx | w,x ∈ Q}，起始狀態為A_q0,F。

步驟1 − 對於每個w, x, y, z ∈ Q，m ∈ S以及a, b ∈ ∑，如果δ (w, a, ε)包含(y, m)並且(z, b, m)包含(x, ε)，則在語法G中新增產生式規則X_wx → a X_yzb。

步驟2 − 對於每個w, x, y, z ∈ Q，在語法G中新增產生式規則X_wx → X_wyX_yx。

步驟3 − 對於w ∈ Q，在語法G中新增產生式規則X_ww → ε。

下推自動機和解析

解析用於使用語法的產生式規則推匯出一個字串。它用於檢查字串的可接受性。編譯器用於檢查字串在語法上是否正確。解析器獲取輸入並構建語法樹。

解析器可以分為兩種型別−

• 自頂向下解析器 − 自頂向下解析從起始符號開始，使用語法樹推匯出一個字串。

• 自底向上解析器 − 自底向上解析從字串開始，使用語法樹到達起始符號。

自頂向下解析器的設計

對於自頂向下解析，PDA有以下四種類型的轉移−

• 彈出棧頂產生式左側的非終結符，並壓入其右側的字串。

• 如果棧頂符號與正在讀取的輸入符號匹配，則將其彈出。

• 將起始符號“S”壓入棧中。

• 如果輸入字串已完全讀取且棧為空，則進入最終狀態“F”。

示例

為表示式“x+y*z”設計一個自頂向下解析器，該表示式對應於具有以下產生式規則的語法G−

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

解答

如果PDA為(Q, ∑, S, δ, q₀, I, F)，則自頂向下解析為−

(x+y*z, I) ⊢(x +y*z, SI) ⊢ (x+y*z, S+XI) ⊢(x+y*z, X+XI)

⊢(x+y*z, Y+X I) ⊢(x+y*z, x+XI) ⊢(+y*z, +XI) ⊢ (y*z, XI)

⊢(y*z, X*YI) ⊢(y*z, y*YI) ⊢(*z,*YI) ⊢(z, YI) ⊢(z, zI) ⊢(ε, I)

自底向上解析器的設計

對於自底向上解析，PDA有以下四種類型的轉移−

• 將當前輸入符號壓入棧中。

• 將棧頂產生式的右側替換為其左側。

• 如果棧頂元素與當前輸入符號匹配，則將其彈出。

• 如果輸入字串已完全讀取，並且只有起始符號“S”保留在棧中，則將其彈出並進入最終狀態“F”。

示例

為表示式“x+y*z”設計一個自頂向下解析器，該表示式對應於具有以下產生式規則的語法G−

P: S → S+X | X, X → X*Y | Y, Y → (S) | id

解答

如果PDA為(Q, ∑, S, δ, q₀, I, F)，則自底向上解析為−

(x+y*z, I) ⊢ (+y*z, xI) ⊢ (+y*z, YI) ⊢ (+y*z, XI) ⊢ (+y*z, SI)

⊢(y*z, +SI) ⊢ (*z, y+SI) ⊢ (*z, Y+SI) ⊢ (*z, X+SI) ⊢ (z, *X+SI)

⊢ (ε, z*X+SI) ⊢ (ε, Y*X+SI) ⊢ (ε, X+SI) ⊢ (ε, SI)

圖靈機簡介

圖靈機是一種接受裝置，它接受由0型語法生成的語言（遞迴可列舉集）。它由艾倫·圖靈於1936年發明。

定義

圖靈機（TM）是一個數學模型，它由一條無限長的帶組成，該帶被分成單元格，並在其上給出輸入。它包含一個讀取輸入帶的磁頭。一個狀態暫存器儲存圖靈機的狀態。讀取輸入符號後，將其替換為另一個符號，其內部狀態發生變化，並且它從一個單元格移動到右側或左側。如果TM到達最終狀態，則接受輸入字串，否則拒絕。

TM可以正式描述為一個7元組(Q, X, ∑, δ, q₀, B, F)，其中−

• Q是狀態的有限集

• X是帶字母表

• ∑是輸入字母表

• δ是轉移函式；δ : Q × X → Q × X × {左移，右移}。

• q₀是初始狀態

• B是空白符號

• F是最終狀態集

與先前自動機的比較

下表顯示了圖靈機與有限自動機和下推自動機的區別。

圖靈機的示例

圖靈機M = (Q, X, ∑, δ, q₀, B, F)，其中

• Q = {q₀, q₁, q₂, q_f}
• X = {a, b}
• ∑ = {1}
• q₀ = {q₀}
• B = 空白符號
• F = {q_f }

δ由下給出−

這裡轉移1Rq₁表示寫入符號為1，磁帶向右移動，下一個狀態為q₁。類似地，轉移1Lq₂表示寫入符號為1，磁帶向左移動，下一個狀態為q₂。

圖靈機的時間和空間複雜度

對於圖靈機，時間複雜度是指當機器初始化某些輸入符號時磁帶移動次數的度量，空間複雜度是寫入的磁帶單元格的數量。

所有合理函式的時間複雜度−

T(n) = O(n log n)

TM的空間複雜度−

S(n) = O(n)

接受語言和判定語言

如果TM對於任何輸入字串w進入最終狀態，則它接受該語言。如果語言被圖靈機接受，則它是遞迴可列舉的（由0型語法生成）。

如果TM接受語言並且對於語言中不存在的任何輸入進入拒絕狀態，則它判定該語言。如果語言被圖靈機判定，則它是遞迴的。

在某些情況下，TM可能不會停止。這樣的TM接受語言，但它不判定它。

設計圖靈機

下面藉助幾個例子解釋了設計圖靈機的一些基本指南。

示例1

設計一個TM來識別所有包含奇數個α的字串。

解答

圖靈機M可以透過以下步驟構建−

• 令q₁為初始狀態。

• 如果M處於q₁狀態；掃描α時，它進入狀態q₂並寫入B（空白）。

• 如果M處於q₂狀態；掃描α時，它進入狀態q₁並寫入B（空白）。

• 從上述步驟可以看出，如果M掃描偶數個α，則它進入狀態q₁，如果它掃描奇數個α，則它進入狀態q₂。因此q₂是唯一的接受狀態。

因此，

M = {{q₁, q₂}, {1}, {1, B}, δ, q₁, B, {q₂}}

其中δ由下給出−

示例2

設計一個圖靈機，讀取表示二進位制數的字串，並擦除字串中的所有前導0。但是，如果字串僅包含0，則保留一個0。

解答

讓我們假設輸入字串以字串兩端的空白符號B結尾。

圖靈機M可以透過以下步驟構建−

• 令q₀為初始狀態。

• 如果M處於q₀狀態，讀取0時，它向右移動，進入狀態q₁並擦除0。讀取1時，它進入狀態q₂並向右移動。

• 如果M處於q₁狀態，讀取0時，它向右移動並擦除0，即用B替換0。到達最左邊的1時，它進入q₂並向右移動。如果它到達B，即字串僅包含0，則它向左移動並進入狀態q₃。

• 如果M處於q₂狀態，讀取0或1時，它向右移動。到達B時，它向左移動並進入狀態q₄。這驗證了字串僅包含0和1。

• 如果M處於q₃狀態，它將B替換為0，向左移動併到達最終狀態q_f。

• 如果M處於q₄狀態，無論讀取0還是1，它都會向左移動。當到達字串的開頭，即讀取B時，它到達最終狀態q_f。

因此，

M = {{q₀, q₁, q₂, q₃, q₄, q_f}, {0,1, B}, {1, B}, δ, q₀, B, {q_f}}

其中δ由下給出−

多磁帶圖靈機

多磁帶圖靈機有多個磁帶，每個磁帶都由一個單獨的磁頭訪問。每個磁頭可以獨立於其他磁頭移動。最初，輸入在磁帶1上，其他磁帶為空白。首先，第一條磁帶被輸入佔用，其他磁帶保持空白。接下來，機器讀取其磁頭下連續的符號，圖靈機在每個磁帶上列印一個符號並移動其磁頭。

多磁帶圖靈機可以正式描述為一個6元組 (Q, X, B, δ, q₀, F)，其中 -

• Q是狀態的有限集

• X是帶字母表

• B是空白符號

• δ 是一個關於狀態和符號的關係，其中

  δ: Q × X^k → Q × (X × {左移, 右移, 不移動 })^k

  其中有k個磁帶

• q₀是初始狀態

• F是最終狀態集

注意 - 每個多磁帶圖靈機都有一個等價的單磁帶圖靈機。

多軌跡圖靈機

多軌跡圖靈機，一種特定型別的多磁帶圖靈機，包含多條軌跡，但只有一個磁頭讀取和寫入所有軌跡。在這裡，一個磁頭在一個步驟中從n條軌跡讀取n個符號。它接受遞迴可列舉語言，就像普通的單軌單磁帶圖靈機一樣。

多軌跡圖靈機可以正式描述為一個6元組 (Q, X, ∑, δ, q₀, F)，其中 -

• Q是狀態的有限集

• X是帶字母表

• ∑是輸入字母表

• δ 是一個關於狀態和符號的關係，其中

  δ(Q_i, [a₁, a₂, a₃,....]) = (Q_j, [b₁, b₂, b₃,....], 左移 或 右移)

• q₀是初始狀態

• F是最終狀態集

注意 - 對於每個單軌圖靈機S，都存在一個等價的多軌跡圖靈機M，使得L(S) = L(M)。

非確定性圖靈機

在非確定性圖靈機中，對於每個狀態和符號，圖靈機都可以有一組動作。因此，這裡的轉換不是確定性的。非確定性圖靈機的計算是從起始配置可以到達的配置樹。

如果樹中至少有一個節點是接受配置，則接受輸入，否則不接受。如果計算樹的所有分支在所有輸入上都停止，則非確定性圖靈機稱為判定機，如果對於某些輸入，所有分支都被拒絕，則該輸入也被拒絕。

非確定性圖靈機可以正式定義為一個6元組 (Q, X, ∑, δ, q₀, B, F)，其中 -

• Q是狀態的有限集

• X是帶字母表

• ∑是輸入字母表

• δ 是一個轉移函式；

  δ : Q × X → P(Q × X × {左移, 右移}).

• q₀是初始狀態

• B是空白符號

• F是最終狀態集

半無限帶圖靈機

具有半無限磁帶的圖靈機有一個左端但沒有右端。左端以一個結束標記限制。

它是一個雙軌磁帶 -

• 上軌跡 - 它表示初始磁頭位置右側的單元格。

• 下軌跡 - 它表示初始磁頭位置左側的單元格，順序相反。

無限長的輸入字串最初以連續的磁帶單元格寫入磁帶上。

機器從初始狀態q₀開始，磁頭從左端標記“End”開始掃描。在每個步驟中，它讀取磁頭下磁帶上的符號。它在該磁帶單元格上寫入一個新符號，然後它將磁頭向左或向右移動一個磁帶單元格。一個轉移函式決定要採取的動作。

它有兩個特殊狀態，稱為接受狀態和拒絕狀態。如果在任何時候它進入接受狀態，則接受輸入；如果它進入拒絕狀態，則圖靈機拒絕輸入。在某些情況下，它會無限期地執行，而不會被接受或拒絕某些特定的輸入符號。

注意 - 具有半無限磁帶的圖靈機等價於標準圖靈機。

線性有界自動機

線性有界自動機是一種多軌跡非確定性圖靈機，其磁帶具有一定的有界有限長度。

長度 = 函式 (初始輸入字串的長度, 常數 c)

這裡，

記憶體資訊 ≤ c × 輸入資訊

計算被限制在常數有界區域。輸入字母表包含兩個特殊符號，用作左端標記和右端標記，這意味著轉換既不移動到左端標記的左側，也不移動到磁帶右端標記的右側。

線性有界自動機可以定義為一個8元組 (Q, X, ∑, q₀, ML, MR, δ, F)，其中 -

• Q是狀態的有限集

• X是帶字母表

• ∑是輸入字母表

• q₀是初始狀態

• M_L 是左端標記

• M_R 是右端標記，其中 M_R ≠ M_L

• δ 是一個轉移函式，它將每個 (狀態, 磁帶符號) 對對映到 (狀態, 磁帶符號, 常數 'c')，其中 c 可以是 0 或 +1 或 -1

• F是最終狀態集

確定性線性有界自動機總是上下文相關的，並且具有空語言的線性有界自動機是不可判定的。

語言可判定性

如果存在一個圖靈機接受並停止每個輸入字串w，則稱語言可判定或遞迴。每個可判定語言都是圖靈可接受的。

如果所有“是”例項到P的語言L是可判定的，則判定問題P是可判定的。

對於可判定語言，對於每個輸入字串，圖靈機要麼在接受狀態要麼在拒絕狀態停止，如下面的圖所示 -

示例1

找出以下問題是否可判定 -

數字“m”是否為素數？

解答

素數 = {2, 3, 5, 7, 11, 13, …………..}

從“2”開始，將數字“m”除以“2”到“√m”之間的所有數字。

如果這些數字中的任何一個產生餘數為零，則它進入“拒絕狀態”，否則它進入“接受狀態”。因此，這裡答案可以用“是”或“否”給出。

因此，這是一個可判定問題。

示例2

給定一個正則語言L和字串w，我們如何檢查w ∈ L？

解答

獲取接受L的DFA，並檢查w是否被接受

一些其他的可判定問題是 -

• DFA是否接受空語言？
• 對於正則集，L₁ ∩ L₂ = ∅ 是否成立？

注意 -

• 如果語言L是可判定的，則其補集L'也是可判定的

• 如果語言是可判定的，則它有一個列舉器。

不可判定語言

對於不可判定語言，不存在任何圖靈機接受該語言並對每個輸入字串w做出決策（儘管圖靈機可以對某些輸入字串做出決策）。如果所有“是”例項到P的語言L不可判定，則判定問題P稱為“不可判定”。不可判定語言不是遞迴語言，但有時它們可能是遞迴可列舉語言。

示例

• 圖靈機的停機問題
• 死亡問題
• 死亡矩陣問題
• Post對應問題等。

圖靈機停機問題

輸入 - 圖靈機和一個輸入字串w。

問題 - 圖靈機是否在有限步數內完成字串w的計算？答案必須是“是”或“否”。

證明 - 首先，我們將假設存在這樣的圖靈機來解決這個問題，然後我們將證明它自相矛盾。我們將這個圖靈機稱為停機機，它在有限的時間內產生“是”或“否”。如果停機機在有限時間內完成，則輸出為“是”，否則為“否”。以下是停機機的框圖 -

現在我們將設計一個反向停機機 (HM)’ 如下 -

• 如果H返回YES，則無限迴圈。

• 如果H返回NO，則停止。

以下是“反向停機機”的框圖 -

此外，一個輸入為自身的機器(HM)₂構造如下 -

• 如果 (HM)₂ 在輸入上停止，則無限迴圈。
• 否則，停止。

這裡，我們得到了一個矛盾。因此，停機問題是不可判定的。

Rice定理

Rice定理指出，由圖靈機識別的任何語言的非平凡語義屬性都是不可判定的。屬性 P 是滿足該屬性的所有圖靈機的語言。

形式定義

如果 P 是一個非平凡屬性，並且儲存該屬性的語言 L_p 被圖靈機 M 識別，則 L_p = {<M> | L(M) ∈ P} 是不可判定的。

描述和屬性

• 語言的屬性 P 僅僅是一組語言。如果任何語言屬於 P (L ∈ P)，則稱 L 滿足屬性 P。

• 如果一個屬性不被任何遞迴可列舉語言滿足，或者被所有遞迴可列舉語言滿足，則稱該屬性是平凡的。

• 非平凡屬性被一些遞迴可列舉語言滿足，而被其他語言不滿足。正式地說，在一個非平凡屬性中，其中 L ∈ P，以下兩個屬性都成立

  • 屬性 1 - 存在圖靈機 M1 和 M2 識別相同的語言，即 ( <M1>, <M2> ∈ L ) 或 ( <M1>,<M2> ∉ L )

  • 屬性 2 - 存在圖靈機 M1 和 M2，其中 M1 識別該語言而 M2 不識別，即 <M1> ∈ L 且 <M2> ∉ L

證明

假設屬性 P 是非平凡的，並且 φ ∈ P。

由於 P 是非平凡的，至少有一種語言滿足 P，即 L(M₀) ∈ P ，∋ 圖靈機 M₀。

設 w 是一個特定時刻的輸入，N 是一個遵循以下規則的圖靈機 -

在輸入 x 上

• 在 w 上執行 M
• 如果 M 不接受（或不停止），則不接受 x（或不停止）
• 如果 M 接受 w，則在 x 上執行 M₀。如果 M₀ 接受 x，則接受 x。

一個將例項 ATM = {<M,w>| M 接受輸入 w} 對映到 N 的函式，使得

• 如果 M 接受 w 且 N 接受與 M₀ 相同的語言，則 L(M) = L(M₀) ∈ p
• 如果 M 不接受 w 且 N 接受 φ，則 L(N) = φ ∉ p

由於 A_TM 是不可判定的，並且可以歸約到 Lp，因此 Lp 也是不可判定的。

Post對應問題

Post對應問題 (PCP)，由 Emil Post 於 1946 年提出，是一個不可判定的決策問題。字母表 ∑ 上的 PCP 問題陳述如下 -

給定以下兩個列表M和N，它們是非空字串在 ∑ 上的列表 -

M = (x₁, x₂, x₃,………, x_n)

N = (y₁, y₂, y₃,………, y_n)

如果對於某些 i₁,i₂,………… i_k，其中 1 ≤ i_j ≤ n，條件 x_i1 …….x_ik = y_i1 …….y_ik 滿足，則可以說存在一個Post對應解。

示例1

找出列表

M = (abb, aa, aaa) 和 N = (bba, aaa, aa)

是否具有Post對應解？

解答

這裡，

x₂x₁x₃ = ‘aaabbaaa’

和 y₂y₁y₃ = ‘aaabbaaa’

我們可以看到

x₂x₁x₃ = y₂y₁y₃

因此，解是i = 2, j = 1, 且 k = 3。

示例2

找出列表M = (ab, bab, bbaaa)和N = (a, ba, bab)是否具有Post對應解？

解答

在這種情況下，沒有解，因為 -

| x₂x₁x₃ | ≠ | y₂y₁y₃ | （長度不相等）

因此，可以說這個Post對應問題是不可判定的。