theory - 将右递归语法翻译成乔姆斯基范式

Question

我正在尝试做一个练习，将语法翻译成乔姆斯基范式。我知道在正常情况下如何做到这一点，但这次我使用的语法是正确的递归。（从技术上讲，语法是前一个问题的答案，所以我可能只是有错误的伽玛。）

我想我可以通过使用固定的规则序列代替 ε 规则来做到这一点，但我想确保我没有走错方向。用一个例子更容易解释：

对于产生 n 'a 的语法，其中 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 -> a替换所有出现的终结符 a ，其中A不在规则集中出现；(2)通过包含新变量的长度为 2 的规则转换所有规则A -> w，其中len (w) > 2。

然后，对于您的A规则，构造一个用于派生终端的规则，例如K -> a，并替换所有出现的终端a：

A -> AKKK

然后将语法放入CNF

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