)下推自动机
PDA的动作由三个因素决定:（1）当前所处状态；
（2）读头所指符号；（3）下推栈栈顶符号。
定义：PDA定义为一七元组
M=（Q，，H，，q0，z0，F），其中：
Q为控制器的有穷状态集；
是一个有穷字母表；
q0Q是控制器的初始状态；
H是下推字母表；
Z0H是下推栈的初始符；
FQ是一终止状态集；
是转换函数，是在 Q（{}）HQH*的映射。转换函数为：
（q，a，z）={（q1，1），（q2，2），…（qn，n）}
其中q，qiQ，a*，zH。其意义是，控制器当前状态为q，下推栈栈顶符号为z，输入符号为a（可为）情况下，状态转换到序偶集。这个序偶集由（qi，i）组成，其中qi下一状态，i为代替z的栈顶符号串，注意要用i的逆串放入栈中。
推自动机和上下文无关文法
设有文法G【A】：
AA（A）
不难看出该文法对应的语言是成对括号串的集合，如
（），（（）），（）（），（（）（））（），（（）（（）））……
能识别该文法定义的语言的自动机为：
( ( ( (
S0 S1 S2 …. Sn
) ) ) )
显然该自动机只能识别嵌套层数为K的成对括号串，若增加了一层嵌套，则需要在自动机的右端增加一个新的状态，随着嵌套层次的增加，状态要增加
