下推自動機

下推自動機PDA的模型是由一條輸入帶，一個有窮控制器和一個下推棧組成。

因素

PDA的動作由三個因素決定:（1）當前所處狀態；
（2）讀頭所指符號；（3）下推棧棧頂符號。
定義：PDA定義為一七元組
M=（Q，，H，，q0，z0，F），其中：
Q為控制器的有窮狀態集；
是一個有窮字母表；
q0Q是控制器的初始狀態；
H是下推字母表；
Z0H是下推棧的初始符；
FQ是一終止狀態集；
是轉換函式，是在 Q（{}）HQH*的映射。轉換函式為：
（q，a，z）={（q1，1），（q2，2），…（qn，n）}
其中q，qiQ，a*，zH。其意義是，控制器當前狀態為q，下推棧棧頂符號為z，輸入符號為a（可為）情況下，狀態轉換到序偶集。這個序偶集由（qi，i）組成，其中qi下一狀態，i為代替z的棧頂符號串，注意要用i的逆串放入棧中。
推自動機和上下文無關文法
設有文法G【A】：
AA（A）
不難看出該文法對應的語言是成對括弧串的集合，如
（），（（）），（）（），（（）（））（），（（）（（）））……
能識別該文法定義的語言的自動機為：
(( ( (
S0 S1S2 …. Sn
)) ) )
顯然該自動機只能識別嵌套層數為K的成對括弧串，若增加了一層嵌套，則需要在自動機的右端增加一個新的狀態，隨著嵌套層次的增加，狀態要增加