为什么这不是CFG？

Question

虽然这是this的翻版，但我说的是个人数字助理的设计。

现在，我知道我错了，因为这是一个广为人知的例子，但我在下面的PDA设计中哪里出了问题？

我想接受language {a^n b^n c^n: n>=0}

每次我遇到一个1时，我都会把两个a推入栈中，为b弹出一个，为c弹出一个，并检查我是否有一个空的栈。

(q0, a, Z) = (q0, 11Z)

(q0, a, 1) = (q0, 111)

(q0, b, 1) = (q1, delta)

(q1, c, 1) = (q2, delta)

(q2, delta, Z) = (q-Final, Z) (epsilon move)

Z is empty stack

这个PDA不接受这样的语言吗？

Answer 1

您的PDA接受以下语言：

{a^n b^i c^j; n >= 0 and i + j = 2n}

它与上述语言的子集{a^n b^n c^n: n>=0}不同，特别是当i = n和j = n时。