翻译权递归语法为乔姆斯基范式

Question

我试图做一个练习，我翻译了语法为Chomsky范式。我知道如何做到这一点在正常情况下，但这次的语法我一起工作是正确的递归。 （技术上语法是回答前一个问题，所以我可能只是有错误的伽马）。

我想我可以代替ε规则使用的规则，一个固定的顺序做，但我要确保我不会在错误的方向前进。它更容易用一个例子来解释：

有关产生N“的其中n是大于0和三的倍数一个语法：（不用担心，这是完全不同的语法我的实际运动）

S-> Aaaa
A-> Aaaa
A-> ε

将正确的翻译是：

S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a

Answer 1

虽然你的语法是正确的递归，您可以执行乔姆斯基范式转变，就像任何其他（非递归右）文法。只需按照你的书，这可能包括两个步骤概述的算法：（1）更换终端的所有出现的在的通过规则的 A - >一个的，其中的甲不会发生在规则集; （2）变换的所有规则的 A - >瓦特，其中 len个（W）> 2，由含有新鲜变量长度为2的规则

有关的 A 的规则，则，构造用于导出端子的规则，说的K - >一，和取代的所有匹配的终端一：

A -> AKKK

然后把语法为CNF

A    -> AA'
A'   -> KA''
A''  -> KK