loops - 从无上下文转换为 CNF 时如何处理循环？

Question

假设有一个语法

• S -> PQT
• R->T
• U -> AU | bX
• X -> Y
• P -> bQ
• Y -> SX | c | X
• Q -> 阿里
• T -> U

有一个循环：

• X -> Y
• Y -> X

转换为CNF时如何消除它？我认为在语法中添加规则（如在单元消除中）X -> X 是不好的，对，因为它基本上是另一个循环？

Answer 1

如果X -> Y和Y -> X，非终结符号是可互换的，您可以安全地将两者中的任何一个的所有实例替换为两者中的另一个，从而完全消除两者中的一个。正如您还指出的那样，X -> X可以安全地消除形式规则。所以这个语法相当于你给的那个：

S -> PQT
R -> T
U -> aU | bX
P -> bQ
X -> SX | c
Q -> aRX
T -> U

这个也是：

S -> PQT
R -> T
U -> aU | bY
P -> bQ
Y -> SY | c
Q -> aRY
T -> U