computer-science - 乔姆斯基范式 - 计算理论

Question

我想将语法更改为乔姆斯基范式（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

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

Answer 1

一个错误是您删除了S --> ɛ转换。你需要那个（S --> ɛ在 CNF 中特别允许，即使AnyNonTerminalOtherThanS --> ɛ不是）。

那么规则[A] --> [a]，应该是[A] --> a因为如果你在 RHS 上只有一个项目，它需要是一个终端。

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

这两个似乎是拼写错误A并且s不存在。你可能的意思是：

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

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