为什么这不是CFG？

Question

尽管这是对this的重新评估，但我正在谈论设计PDA。

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

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

每次我遇到一个a时间推栈上的两个1的，弹出一个用于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。