乔姆斯基范式

---

如果产生式采用以下形式，则 CFG 处于乔姆斯基范式 -

• 一个→一个
• 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出现在 RHS 中，我们添加一个新的状态S ₀ ，并将S ₀ →S添加到生产集中，变成 -

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

(2)现在我们将删除空产生式 -

B → ε 且 A → ε

去除 B → ε 后，产生式集变为 -

S ₀ →S, S→ ASA | 乙 | a, A → B | S | ε, B → b

删除 A → ε 后，产生式集变为 -

S ₀ →S, S→ ASA | 乙 | 一个 | 作为| 南澳 | S，A → B | S，B→b

(3)现在我们将删除单元产生式。

删除 S → S 后，产生式集变为 -

S ₀ →S, S→ ASA | 乙 | 一个 | 作为| 南，A → B | S，B→b

去掉 S ₀ → S 后，产生式集变为 -

S ₀ → ASA | 乙 | 一个 | 作为| SA、S→ ASA | 乙 | 一个 | 作为| SA

A → B | S，B→b

移除 A→ B 后，产生式集变为 -

S ₀ → ASA | 乙 | 一个 | 作为| SA、S→ ASA | 乙 | 一个 | 作为| SA

A → S | 乙

乙 → 乙

去除 A→ S 后，产生式集变为 -

S ₀ → ASA | 乙 | 一个 | 作为| SA、S→ ASA | 乙 | 一个 | 作为| SA

A → b |ASA | 乙 | 一个 | 作为| SA，B → b

(4)现在我们将在RHS中找出两个以上的变量

这里，S ₀ → ASA，S → ASA，A→ ASA 违反了 RHS 中的两个非终结符

因此，我们将应用步骤 4 和步骤 5 来获得以下 CNF 中的最终产生式集 -

S ₀ → AX | 乙 | 一个 | 作为| SA

S→ AX | 乙 | 一个 | 作为| SA

A → b |AX | 乙 | 一个 | 作为| SA

乙 → 乙

X → 南

(5)我们必须改变产生式 S ₀ → aB, S→ aB, A→ aB

最终的生产集变成 -

S ₀ → AX | YB | 一个 | 作为| SA

S→ AX | YB | 一个 | 作为| SA

A → b A → b |AX | YB | 一个 | 作为| SA

乙 → 乙

X → 南

Y→a