文章/答案/技术大牛

发布

社区首页 >问答首页 >乔姆斯基范式--计算理论

问乔姆斯基范式--计算理论
EN

Stack Overflow用户

提问于 2010-12-14 01:23:09

回答 1查看 925关注 0票数 1

我想把语法改成乔姆斯基范式(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

我对答案不太确定。谁能告诉我这是对还是错？

发布于 2010-12-14 01:32:32

一个错误是您删除了S --> ɛ转换。您需要这样做( CNF中特别允许使用S --> ɛ，尽管AnyNonTerminalOtherThanS --> ɛ不允许)。

那么规则[A] --> [a]应该是[A] --> a，因为如果您在RHS上只有一个条目，那么它必须是一个终端。

[aA] --> [a] A
[Sb] --> s [b]

这两个看起来像是拼写错误，因为A和s并不存在。你的意思可能是：

[aA] --> [a] [A]
[Sb] --> [S] [b]

除此之外，你所拥有的都是正确的。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/4431553

复制

相似问题

问乔姆斯基范式--计算理论EN