PDA 的非確定性（nondeterminism）

和 NFA 一樣，一般的下推自動機是非確定性的：在某一時刻它可能有「好幾個」合法動作可選，而只要「某一」串選擇能導向接受，它就接受。把它想成複製自己以平行嘗試所有選項，或想成一位幸運的猜測者，只要存在正確的分支，他總能挑中它。這種猜測能力，配上堆疊，正是 PDA 處理某些上下文無關語言所需。

為什麼這裡的猜測不可或缺？考慮 {a, b} 上的偶數長度迴文語言——像 abba 或 baab 這種正讀反讀都一樣的字串。要檢查一個迴文，PDA 把前半段推入堆疊，再一邊彈出一邊與後半段比對；由於堆疊會反轉順序，這樣剛好行得通。但機器並沒有任何標記告訴它中點在哪。它必須在某一點「猜測」：「前半段結束了，現在開始比對」。非確定型 PDA 就是同時嘗試每一個可能的中點，只要有任何一個猜測成功就接受。中點無法事先計算出來，所以這個猜測是真的必要。

這正是下推自動機在深層意義上與有限自動機分道揚鑣的時刻。對有限自動機而言，非確定性只是便利——每個 NFA 都能轉成等價的 DFA。但對下推自動機這是「錯的」：非確定型 PDA 嚴格地比確定型更強大。偶數長度迴文是上下文無關的，可由非確定型 PDA 辨識，卻沒有任何確定型 PDA 能辨識它。所以這裡的非確定性不只是便利；它增添了真正的表達力，而這種不對稱是整個理論中最令人驚訝的事實之一。