乔姆斯基范式 - 计算理论
我想将语法更改为乔姆斯基范式（CNF）。
这是
S--> AB | ɛ
A--> aASb | a
B--> bS
我尝试解决这个问题
S --> [A] [B]
[A] --> [aA] [Sb] | [a]
[aA] --> [a] A
[Sb] --> s [b]
[a] --> a
[b] --> b
的例子，我不确定答案。有人能告诉我这是对还是错吗？
I want to change the grammar in to Chomsky Normal Form(CNF).
This is example
S--> AB | ɛ
A--> aASb | a
B--> bS
I try to solve this
S --> [A] [B]
[A] --> [aA] [Sb] | [a]
[aA] --> [a] A
[Sb] --> s [b]
[a] --> a
[b] --> b
I am not sure about the answer. Could anybody tell me if it is right or wrong?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
一个错误是您删除了
S -->; ɛ 过渡。您需要它（CNF 中明确允许S --> ɛ，尽管AnyNonTerminalOtherThanS --> ɛ不允许）。然后规则
[A] --> [a]，应该是[A] --> a因为如果 RHS 上只有一项，那么它必须是终端。这两个看起来像是拼写错误，因为
A和s不存在。您可能的意思是：除此之外，您拥有的都是正确的。
One mistake is that you removed the
S --> ɛtransition. You need that (S --> ɛis specifically allowed in CNF, even thoughAnyNonTerminalOtherThanS --> ɛis not).Then the rule
[A] --> [a], should be[A] --> abecause if you have only one item on the RHS, it needs to be a terminal.These two seem like typos as
Aandsdon't exist. You probably meant:Other than that, what you have is correct.
将乔姆斯基范式写成上述问题..
获取形式为 S->AB （或）S->aB
[aA] --> [一] [一]
[Sb]--> [S] [b]
To write Chomsky normal form to the above question..
Get the form to either S->AB (or) S->aB
[aA] --> [a] [A]
[Sb] --> [S] [b]
[乔姆斯基范式][1]
点击此处查看乔姆斯基范式示例
[1]: https://i.sstatic.net/F44H0.jpg
[Chomsky normal form][1]
Click on this to see the example of chomsky normal form
[1]: https://i.sstatic.net/F44H0.jpg