乔姆斯基范式

---

---

如果产生式具有以下形式，则 CFG 处于乔姆斯基范式：

• A → a
• 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 | aB | a, A → B | S | ∈, B → b

删除 A → ∈ 后，产生式集合变为：

S₀→S, S→ ASA | aB | a | AS | SA | S, A → B | S, B → b

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

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

S₀→S, S→ ASA | aB | a | AS | SA, A → B | S, B → b

删除 S₀→ S 后，产生式集合变为：

S₀→ ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

A → B | S, B → b

删除 A→ B 后，产生式集合变为：

S₀ → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

A → S | b

B → b

删除 A→ S 后，产生式集合变为：

S₀ → ASA | aB | a | AS | SA, S→ ASA | aB | a | AS | SA

A → b |ASA | aB | a | AS | SA, B → b

(4) 现在我们将找出 RHS 中超过两个变量的情况

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

因此，我们将应用步骤 4 和步骤 5 以获得以下最终产生式集合，它处于 CNF：

S₀→ AX | aB | a | AS | SA

S→ AX | aB | a | AS | SA

A → b |AX | aB | a | AS | SA

B → b

X → SA

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

最终产生式集合变为：

S₀→ AX | YB | a | AS | SA

S→ AX | YB | a | AS | SA

A → b A → b |AX | YB | a | AS | SA

B → b

X → SA

Y → a