下推自動機

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 S1 S2 …. Sn

) ) ) )

顯然該自動機只能識別嵌套層數為K的成對括弧串，若增加了一層嵌套，則需要在自動機的右端增加一個新的狀態，隨著嵌套層次的增加，狀態要增加