作為記憶體的堆疊

想像一疊裝在彈簧托盤上的自助餐盤：你永遠只能把盤子放在「最上面」，或拿走「最上面」那一個——你伸不進中間或底部。這就是堆疊，也是下推自動機在有限控制之外唯一多出來的記憶體。把它稱作「記憶體」再貼切不過：它讓機器能記住東西，但是以嚴格紀律、後進先出的方式進行。

有兩項性質使這種記憶體特別。第一，它是「無界的」：堆疊可以長到所需的任意高度，所以機器能記住任意大量的資訊——例如為 n 個輸入符號各放一個標記，對 n 沒有固定上限。第二，它的存取是「受限的」：任一時刻機器只能看見並修改最上面的符號；底下的一切都看不見、碰不到，直到上面的東西被彈出為止。所以 PDA 能儲存大量資訊，但只能以「與存入相反的順序」來查閱。

這個組合正好是巢狀、遞迴結構的甜蜜點。配對括號、平衡的 begin／end 區塊，以及一連串待處理的副程式呼叫，都有「最近開啟者必須最先閉合」的性質——這恰恰就是後進先出。這也正是為什麼堆疊對某些任務太弱：只能碰最上面這項限制，意味著 PDA 無法自由比對相隔很遠的資訊，這就是它無法辨識像 a^n b^n c^n 那種需同時計數三個量的語言的深層原因。