資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究將給定的上下文無關文法轉換為 Chomsky 正規化 (CNF)
問題
將給定的語法轉換為 Chomsky 正規化 (CNF)
S->AAA|B
A->aA|B
B-> ε
解決方案
按照以下步驟將 CFG 轉換為 CNF -
步驟 1 - 消除 ε 生成式
要消除 ε 生成式，必須在所有其他生成式的 RHS 中替換產生 ε 的變數，以移除 ε 生成式。
在所有其他生成式中用 ε 替換 B 得到以下生成式集 -
S-> AAA | ε | B
A->aA | ε | B
在所有其他生成式中用 \epsilon 替換 A 得到以下結果 -
S ->AAA | AA | A | B | ε [分別用 ε 替換 1、2 和 3 個 A]
A->aA | a | B
由於語法生成字串 ε，因此為了使語法保持等價，無法消除剩餘的 ε 生成式。移除最終的 ε 生成式得到一個語法 G'，該語法與原始語法 G 具有以下關係 -
L(G') = L(G) -{ ε }
G' 中的生成式如下 -
S -> AAA | AA | A | B
A -> aA | a | B
步驟 2 - 消除單元生成式
消除單元生成式的過程如下 -
選擇一個生成式 A-> B，使得存在非單元生成式 B-> a
對於每個非單元生成式 B-> a，重複以下步驟 -
向語法中新增生成式 A->a。
從語法中消除 A->B。
從語法中消除單元生成式 S-> A，得到以下語法 -
S ->AAA | AA | aA | a | B
A -> aA | a | B
B 沒有生成式，因此無法消除型別 V -> B 的單元生成式。
步驟 3 - 無用符號
B 是一個無用符號，因為它沒有生成式。因此可以移除它。
A-> a 導致生成一個終結符字串，並且它可以從 S 訪問，因此 A 不是無用的
類似地，S 也不無用，因為可以從中生成終結符。
因此，移除無用符號後的結果 CFG 為 -
S->AAA | AA | aA | a
A->aA | a
Chomsky 正規化 (CNF)
要將語法轉換為 Chomsky 正規化，需要將右側有多於兩個元素的所有生成式拆分為兩個或多個生成式，方法是新增更多變數。
右側至少有兩個符號的生成式中的終結符需要替換為變數符號。
新增以下生成式以生成終結符 a -
Z->a
結果語法如下 -
S-> AAA | AA | ZA | a
A-> ZA | a
Z -> a
生成式 S ->AAA 透過新增一個額外的變數 T 進行修改。
這給出了以下語法 -
S -> TA | AA | ZA | a
T ->AA
A -> ZA | a
Z -> a
在上述語法中，所有生成式都為 A -> BC 或 A ->b 的形式。因此，它處於 Chomsky 正規化 (CNF)。
18K+ 次檢視
