这里的大多数问题似乎都涉及将特定 CFG 转换为 CNF。但我在网上查找并找不到时间复杂度的答案。将任何给定 CFG 转换为乔姆斯基范式的运行时复杂度是多少？是多项式时间吗？
我预计它本质上是指数级的。一个简单的例子可以给出这个下限。考虑产生式规则 S -> ABC...N, A -> a |埃普西隆，B -> b | Epsilon，...现在考虑消除 epsilon 转换的步骤。当我们消除 A -> Epsilon 时，我们得到 S -> ABC...N | BCD...N 作为新的产生式规则。接下来消除 B-> Epsilon，我们得到 S -> ABC...N | BCD...N |交流...N | CD...N。正如您所看到的，可以呈指数级增长。