移動關係（move relation）
/ the turnstile symbol is read "yields" /
如果瞬間描述是機器的快照，那麼移動關係就是規定「哪張快照能接著出現」的規則。它以一個旋轉柵門符號書寫，常打成 |-，讀作「產生（yields）」或「移動到」：一個 ID 在機器的單一合法步驟中「產生」另一個 ID。它把靜態的快照集合變成一部會動的影片。
精確地說，當 δ（delta）中存在一條轉移能正當化此變化時，一個 ID 就產生另一個 ID。若 δ(q, a, X) 允許動作 (p, γ)，則 (q, a w, X β) 產生 (p, w, γ β)：機器消耗了輸入符號 a，從狀態 q 變到 p，並把頂端堆疊符號 X 替換成串 γ，而其餘輸入 w 與其餘堆疊 β 保持不變。ε-移動做同樣的事，但不消耗任何輸入。由於 PDA 是非確定性的，單一 ID 可能產生好幾個不同的 ID。我們也寫它的自反遞移閉包（|- 加上星號）來表示「在零步或多步內產生」——這個關係捕捉的是整段計算，而不只是單一步驟。
這個關係是定義與證明的主力。以終止狀態接受定義為：起始 ID 在零步或多步內產生某個 ID，其狀態屬於 F 且輸入已全部消耗。以空堆疊接受定義為：起始 ID 產生某個 ID，其輸入已全部消耗且堆疊為空。每一條關於 PDA 的定理——兩種接受模式的等價、與文法的等價——歸根究柢都是關於「移動關係連接了哪些 ID」的陳述。
若 δ(q0, a, Z0) = {(q0, X Z0)}，則 (q0, ab, Z0) |- (q0, b, X Z0)：機器讀了 a，留在 q0，並在 Z0 上方推入 X。把這樣的單步接連起來，就構成整段運行。
一個 ID 透過單一轉移 |- 另一個 ID；加星號的版本表示零步或多步。
移動關係一般「不是」函數：非確定型 PDA 可能從一個 ID 同時產生好幾個 ID。一段計算是穿過這個分支關係的一條路徑，而接受只要求「某一條」路徑抵達接受的 ID。