context-free-grammar - 这些上下文无关语法是否等效？

Question

语言是 {w|w has an odd length}，字母表是 {0,1}。

我想出了一个解决方案

S->1p|0p|e

p->00p|11p|01p|10p|e

这本书有

S->0|1|0S0|0S1|1S0|1S1

这些是等价的吗？

Answer 1

他们不是。第一个语法描述了一种包含空字符串的语言；e不应该是扩展的选项S。