context-free-grammar - 为什么这不是CFG？

Question

虽然这是对此的重复，但我是在设计 PDA 方面进行讨论。

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

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

1每次遇到一个a, 弹出一个 forb并弹出一个 for时，我都会在堆栈上压入两个，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。