将右递归语法转换为乔姆斯基范式
我正在尝试做一个练习，将语法翻译成乔姆斯基范式。我知道在正常情况下如何做到这一点，但这次我正在使用的语法是正确的递归。 （从技术上讲，语法是上一个问题的答案，所以我可能只是有错误的伽玛。）
我想我可以通过使用固定的规则序列代替 ε 规则来做到这一点，但我想确保我不是朝着错误的方向前进。用一个例子更容易解释：
对于产生 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
I am trying to do an exercise where I translate a grammar into Chomsky normal form. I understand how to do this in normal circumstances but this time the grammar I am working with is right recursive. (Technically the grammar is the answer to the previous question, so I might just have the wrong gamma.)
I think I can do this by using a fixed sequence of rules in place of ε rules but I want to make sure I'm not heading in the wrong direction. It's easier to explain with an example:
For a grammar that produces n 'a's where n is greater than 0 and a multiple of three: (don't worry, this is entirely different to the grammar my actual exercise)
S-> Aaaa
A-> Aaaa
A-> ε
Would the correct Translation be:
S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
尽管您的语法是右递归的，但您可以像执行任何其他（非右递归）语法一样执行乔姆斯基范式转换。只需遵循书中概述的算法，该算法可能包含两个步骤：(1) 用规则 A -> 替换所有出现的终结符 a。 a，其中 A 未出现在规则集中； (2) 变换所有规则A -> w，其中 len(w) > 2、通过包含新鲜变量的长度2的规则。
然后，对于您的 A 规则，构建一个用于派生终结符的规则，例如 K -> a，并替换所有出现的终端a：
然后将语法放入CNF
Although your grammar is right-recursive, you can perform the Chomsky Normal Form transformation as you would any other (non-right recursive) grammar. Simply follow the algorithm outlined in your book, which probably consists of two steps: (1) replace all occurrences of terminals a by rules A -> a, where A does not occur in the rule set; (2) transform all rules A -> w, where len(w) > 2, by rules of length 2 containing fresh variables.
For your A rule, then, construct a rule for deriving terminals, say K -> a, and replace all occurrences of the terminal a:
Then put the grammar into CNF