
- 自動機理論教程
- 自動機理論 - 首頁
- 自動機理論 - 入門
- 自動機理論 - 歷史
- 自動機理論 - 應用
- 自動機理論術語
- 自動機中字串的基礎
- 自動機的集合論
- 語言和文法
- 計算理論中的文法
- 由文法生成的語言
- 喬姆斯基文法分類
- 有限自動機
- 確定性有限自動機 (DFA)
- 非確定性有限自動機 (NFA)
- 從 NFA 到 DFA 的轉換
- DFA 的最小化
- 穆爾機與米利機
- DFA 的補集
- 正則表示式
- 自動機中的正則表示式
- 自動機中的 Arden 定理
- 將正則表示式轉換為有限自動機
- 正則文法的泵引理
- 計算理論中的正則集
- 上下文無關文法
- 上下文無關文法 (CFG)
- 上下文無關文法中的二義性
- 上下文無關語言的封閉性
- 簡化上下文無關文法
- 喬姆斯基正規化 (CNF)
- 格雷巴赫正規化 (GNF)
- 上下文無關文法的泵引理
- 下推自動機
- 下推自動機 (PDA)
- 下推自動機的接受
- 從 CFG 構造 PDA
- 下推自動機與解析
- 圖靈機
- 圖靈機 (TM) 基礎
- 圖靈機接受的語言
- 多磁帶圖靈機
- 多軌跡圖靈機
- 非確定性圖靈機
- 半無限磁帶圖靈機
- 線性有界自動機 (LBA)
- 可計算性和不可判定性
- 圖靈語言的可判定性
- 不可判定語言
- 圖靈機停機問題
- 計算理論中的 Rice 定理
- Post 對應問題 (PCP)
- 自動機理論資源
- 自動機理論 - 快速指南
- 自動機理論 - 資源
- 自動機理論 - 討論
CFG 簡化
在 CFG 中,可能會發生並非所有產生式規則和符號都用於字串的推導。此外,可能存在一些空產生式和單元產生式。消除這些產生式和符號稱為 **CFG 的簡化**。簡化主要包括以下步驟:
- CFG 的化簡
- 移除單元產生式
- 移除空產生式
CFG 的化簡
CFG 分兩個階段進行化簡:
**階段 1** - 從 CFG **G** 推匯出等價文法 **G’**,使得每個變數都推匯出某個終結符串。
**推導過程** -
步驟 1 - 包含所有推匯出某個終結符的符號 **W1**,並初始化 **i=1**。
步驟 2 - 包含所有推匯出 **Wi** 的符號 **Wi+1**。
步驟 3 - 增加 **i** 並重復步驟 2,直到 **Wi+1 = Wi**。
步驟 4 - 包含所有包含 **Wi** 的產生式規則。
**階段 2** - 從 CFG **G’** 推匯出等價文法 **G”**,使得每個符號都出現在某個句型中。
**推導過程** -
步驟 1 - 將開始符號包含在 **Y1** 中,並初始化 **i = 1**。
步驟 2 - 包含所有可以從 **Yi** 推匯出的符號 **Yi+1**,幷包含所有已應用的產生式規則。
步驟 3 - 增加 **i** 並重復步驟 2,直到 **Yi+1 = Yi**。
問題
找到一個與文法 G 等價的化簡文法,G 具有產生式規則 P:S → AC | B,A → a,C → c | BC,E → aA | e
解答
**階段 1** -
T = { a, c, e }
根據規則 A → a,C → c 和 E → aA,W1 = { A, C, E }
根據規則 S → AC,W2 = { A, C, E } U { S }
W3 = { A, C, E, S } U ∅
由於 W2 = W3,我們可以推匯出 G’ 為:
G’ = { { A, C, E, S }, { a, c, e }, P, {S}}
其中 P:S → AC,A → a,C → c ,E → aA | e
**階段 2** -
Y1 = { S }
根據規則 S → AC,Y2 = { S, A, C }
根據規則 A → a 和 C → c,Y3 = { S, A, C, a, c }
Y4 = { S, A, C, a, c }
由於 Y3 = Y4,我們可以推匯出 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
這是最終不包含空轉換的產生式集。