grammar - 构造生成 L = {a^p b^m c^n|n>=0, m>=0, p=m+n} 的文法

Question

构造生成L的文法:

L = {a^p b^m c^n|n>=0, m>=0, p=m+n}

到目前为止我已经尝试了这么多:

S->A
A->aAb|B
B->aBc|epsilon

我的语法正确吗？

Answer 1

我无法给出数学证明，但让我们尝试枚举您的语法可以生成的字符串:

ε, ac, aacc, aaaccc, ...(更多相同的 a 和 c)，ab, aabb, aaabbb, ...(更多相同的 a 和 b), aacb, aaaccb, aaacbb, aaaaccbb , ...(更多 #a 与 #b + c 相同)

现在:

a^p b^m c^n

表示订单必须严格履行？即首先是 a 然后是 b 然后是 c。如果是，您可以自己看到 b 和 c 实际上在您的语法中交换了。