爲什麼這不是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。