資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學如何將CFG轉換為格雷巴赫正規化？
上下文無關文法 (CFG) 如果其產生式規則滿足以下條件之一，則被稱為格雷巴赫正規化 (GNF)：
只有開始符號可以生成 ε。例如，如果 S 是開始符號，則 S → ε 屬於 GNF。
非終結符可以生成終結符。例如，如果 A 是非終結符，a 是終結符，則 A → a 屬於 GNF。
非終結符可以生成一個終結符，後跟任意數量的非終結符。例如，S → aAS 屬於 GNF。
案例 1
G1 = {S → aAB | aB, A → aA| a, B → bB | b}
G1 的產生式規則滿足 GNF 的規定規則，因此文法 G1 屬於 GNF。
案例 2
G2 = {S → aAB | aB, A → aA | ε, B → bB | ε}
G2 的產生式規則不滿足 GNF 的規定規則，因為：
A → ε 和 B → ε 包含 ε（只有開始符號才能生成 ε）。
因此，文法 G2 不屬於 GNF。
將CFG轉換為GNF的步驟
步驟 1 - 將文法轉換為 Chomsky 正規化 (CNF)。如果給定的文法不是 CNF，則將其轉換為 CNF。
步驟 2 - 如果文法包含左遞迴，則消除它。如果上下文無關文法包含任何左遞迴，則消除它。
步驟 3 - 在文法中，將給定的產生式規則轉換為 GNF 形式。如果文法中任何產生式規則不是 GNF 形式，則將其轉換。
示例
考慮上下文無關文法
S→SS|(S)|a
將此文法轉換為格雷巴赫正規化。
解答
以下是將 CFG 轉換為 GNF 的說明：
Step 1: Converting to CNF: S->SS|XSY|a X->( Y->) Step 2: Remove left recursion from S->SS S->XSYP/aP P->SP/ε X->( Y->) Step 3: Remove null production P->ε S->XSYP/aP P->SP/S X->( Y->) Step 4: Convert to GNF as S->XSYP is not in GNF, Replace X with ( S->(SYP/aP P->SP/S X->( Y->) Step 5: Convert to GNF as P->SP is not in GNF, Replace S with (SYP/aP S->(SYP/aP P->(SYPP/aPP/(SYP/aP X->( Y->)
更新於：2021年6月15日
15K+ 次瀏覽
廣告