如何转换为乔姆斯基范式 (CNF)

Question

如何将以下语法转换为 CNF？

S → ASA | aB

A → B | S

B → b | ε

Answer 1

我们可以将上下文无关文法到 Chomsky 范式的转换分为四个步骤。

1. Bin 步骤确保所有产生式中的所有备选方案包含不超过两个终端或非终端。
2. Del 步骤“删除”所有空字符串标记。
3. Unit 步骤“内联”直接映射到单个非终端的产品。
4. Term 步骤确保终端和非终端不会在任何替代方案中混用。

根据您的示例，描述每个步骤，到 CNF 的转换如下所示。

斌

作品 S 中的备选方案被拆分成更小的作品。新的非终端是 T.

S → AT | aB
A → B | S
B → b | ε
T → SA

删除

从 S 的产生式中，可空非终端 A 和 B 被分解出来。

S → AT | T | aB | a
A → B | S
B → b | ε
T → SA

制作A，无需任何操作。

S → AT | T | aB | a
A → B | S
B → b | ε
T → SA

从 B 的生成中，删除了空字符串标记。

S → AT | T | aB | a
A → B | S
B → b
T → SA

从 T 的产生式中，分解出了可为空的非终结符 A。

S → AT | T | aB | a
A → B | S
B → b
T → SA | S

单位

在 A 中“内联”了 B 的产生式。

S → AT | T | aB | a
A → b | S
B → b
T → SA | S

学期

用新的非终端 U 替换了生产 S 中的终端“a”。

S → AT | T | UB | a
A → b | S
B → b
T → SA | S
U → a

大功告成。