chomsky-normal-form - 如何转换为乔姆斯基范式（CNF）

Question

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

S → ASA | aB

A → B | S

B → b | ε

Answer 1

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

1. Bin步骤确保所有产品中的所有备选方案包含不超过两个终端或非终端。
2. Del步骤“删除”所有空字符串标记。
3. 该单元将直接映射到单个非终端的“内联”产生式步骤。
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

你完成了。