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

Question

如何将下面的语法转换为CNF?

S → ASA | aB
A → B | S
B → b | ε

Answer 1

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

1. Bin步骤确保所有产品中的所有替代方案包含不超过两个终端或非终端。
2. 删除步骤"删除">
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

单位"Inlined"B在a中的生产

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

<<h3>词/h3>更换终端"a"使用新的非终端u

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

你完成了。