下推自动机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                  S1               S2                   ….                      Sn

)             )              )                  )

显然该自动机只能识别嵌套层数为K的成对括号串，若增加了一层嵌套，则需要在自动机的右端增加一个新的状态，随着嵌套层次的增加，状态要增加