grammar - Converting to Chomsky Normal Form from a CFG?

Question

Consider the context-free grammar G = ( { S, B, E }, { 0, 1, i, e, s }, R, S ), where R is:

S --> iBSE | s
B --> 0 | 1
E --> lambda | eS

Alrighty, so I removed the lambda and got:

S0 --> S
S --> iBS | iBSE | s
B --> 0 | 1
E --> eS

And now I'm trying to remove the unit/chain rules and the rest, and this is what I have so far:

S0 --> X
X --> YS
S --> BS
S --> BSE
S --> s
B --> 0
B --> 1
E --> ZS
Y --> i
Z --> e

But I know S0 --> X and S --> BSE are not valid. How can I fix this? Thank you for any help! :)

Answer 1

你创造了X吗？如果是这样，S0-->S是一个更好的主意。然后，要从 S 的右侧删除 S 应该使用非终端来完成。 S0 --> S S --> BS | BSE | s 您想用非终端替换 BS 之类的东西： S --> P | PE | s P --> BS 如果您可以指定上下文是什么（对于 lambda，以及您用于 epsilon 的内容，我可能会提供更多帮助，但是有很多谷歌可以为你找到的计算理论幻灯片，它们本身就很有帮助（如果你得到了正确的）。