兩種接受模式的等價（equivalence of acceptance modes）

有兩個不同的「接受」定義，會引出一個明顯的疑慮：它們描述的是同一批機器嗎？會不會有些語言只能靠檢查最後狀態抓到，另一些只能靠清空堆疊抓到？令人安心的答案是：不會。這兩種接受模式在表達力上「等價」：以終止狀態接受的語言類別，恰好就是以空堆疊接受的語言類別。兩個類別都正是上下文無關語言。

等價性的證明在於展示你可以機械地把一種機器轉換成另一種。要把以空堆疊接受者轉成以終止狀態接受者，你在原本的 Z0 底下加一個特殊的底部標記；每當原機器會把堆疊清空到那個標記時，新機器改以一次 ε-移動進入一個全新的接受狀態。反過來，要把以終止狀態接受者轉成以空堆疊接受者，你讓機器在抵達接受狀態時，跑一段由 ε-移動構成的清理程序，把堆疊上的一切都彈光；那個特殊標記則防止在正常運行中意外清空。每一種轉換都只改外包裝，從不改變語言。

這很重要，因為它讓你能用任一較方便的模式來推理與建構，並確信這個選擇絕不改變哪些語言可被辨識。以空堆疊接受與「文法轉 PDA」的構造配合得天衣無縫；以終止狀態接受則更接近有限自動機，對某台特定機器往往更易推理。正是這個等價，使「該 PDA 辨識 L」成為一個明確的陳述，無論你從哪個定義出發。