首先重申 EPDA 是有一組其自身可以通過「嵌入棧」來訪問的棧的有限狀態機,每個棧包含「棧字母表」
的元素,並且我們通過
定義一個棧的元素,這裡的星號是字母表的Kleene閉包。
每個棧都可以依據它的元素來定義,所以我們使用雙劍符號來指示在自動機中的第
個棧:
,這裡的
將是在棧中的下一個可訪問的符號。
個棧的「嵌入棧」因此可以指示為
。
我們定義 EPDA 為七元組
這裡的
是「狀態」的有限集合;
是「輸入字母表」的有限集合;
是「棧字母表」的有限集合;
是「開始狀態」;
只「最終狀態」的集合;
是「初始棧符號」
是「轉移函數」,這裡的
是
的有限子集。
所以轉移函數選取一個狀態,輸入字符串的下一個符號,和當前棧的頂符號;並生成下一個狀態,在「嵌入棧」上要壓入和彈出的那些棧,當前棧的壓入和彈出,和要在下一個轉移中被當作當前棧的棧。更加概念的說,「嵌入棧」是被壓入和彈出的,當前棧被隨意的壓回到「嵌入棧」,而你希望的任何其他棧將被壓入它的頂部,帶有最後的棧是在下一個重複中所讀取的。所以,這些棧被同時壓入當前棧的上面和下面。
一個給定的格局被定義為

這裡的
是當前狀態,
是在「嵌入棧」中的棧,帶有
是當前棧,而對於輸入字符串
,
是已經被機器處理的那部分字符串,而
是要處理的那部分,帶有它的頭部是當前所讀的符號。注意空串
被隱含的定義為終止符號,如果機器處於最終狀態此時讀到空串,則整個輸入字符串被「接受」,如果不是則「拒絕」。這種「接受」了的字符串是如下語言的元素

這裡的
而
定義轉移函數按需要而多次應用來分析這個字符串。