本文概述
- 将CFG转换为CNF的步骤
- 开始生成符号ε。例如，A→ε。
- 一个非终端生成两个非终端。例如，S→AB。
- 生成终端的非终端。例如，S→a。
G1 = {S → AB, S → c, A → a, B → b}
G2 = {S → aA, A → a, B → c}语法G1的生成规则满足为CNF指定的规则，因此语法G1在CNF中。但是，语法G2的生成规则不满足为CNF指定的规则，因为S→aZ包含终止符，然后是非终止符。因此语法G2不在CNF中。
将CFG转换为CNF的步骤步骤1：从RHS中删除开始符号。如果开始符号T在任何生产的右侧，请创建新生产，如下所示：
S1 → S其中S1是新的开始符号。
步骤2：在语法中，删除空，单位和无用的生产。你可以参考CFG的简化。
步骤3：如果终端与其他非终端或终端一起存在，则从产品的RHS中消除终端。例如，生产S→aA可以分解为：
S → RA
R → a步骤4：使用两个以上的非终端消除RHS。例如，S→ASB可以分解为：
S → RS
R → AS例：
【自动机Chomsky范式（CNF）】将给定的CFG转换为CNF。考虑给定的语法G1：
S → a | aA | B
A → aBB | ε
B → Aa | b解：
步骤1：我们将创建一个新产品S1→S，因为起始符号S出现在RHS上。语法将是：
S1 → S
S → a | aA | B
A → aBB | ε
B → Aa | b步骤2：由于语法G1包含A→ε零产生，因此将其从语法中去除会产生：
S1 → S
S → a | aA | B
A → aBB
B → Aa | b | a现在，由于语法G1包含单位产出S→B，因此其去除率：
S1 → S
S → a | aA | Aa | b
A → aBB
B → Aa | b | a还要去除单位产品S1→S，从语法中去除它会产生：
S0 → a | aA | Aa | b
S → a | aA | Aa | b
A → aBB
B → Aa | b | a步骤3：在生产规则S0→aA | Aa，S→aA | Aa，A→aBB和B→Aa，RHS上的终端a具有非终端。因此我们将终端X替换为：
S0 → a | XA | AX | b
S → a | XA | AX | b
A → XBB
B → AX | b | a
X → a步骤4：在生产规则A→XBB中，RHS有两个以上的符号，将其从语法结果中删除：
S0 → a | XA | AX | b
S → a | XA | AX | b
A → RB
B → AX | b | a
X → a
R → XB因此，对于给定的语法，这是必需的CNF。
