下推自动机

FA 识别正则语言(右线性语言)，PDA识别上下文无关语言。

FA只能处理正则语言，正则文法生成无穷语言是由于 $A\rarr wA$ ，也不需要记录 w 的具体数目。

而无关文法生成无穷语言 $A\rarr \alpha A\beta$ ，需要记录 $\alpha$ 和 $\beta$ 之间的对应关系；FA 循环方式无法保证该对应关系。

利用栈的特点，能够按照一定顺序关系存储，从而使得下推自动机能够记录 $\alpha$ 和 $\beta$ 的对应关系。

PDA 停机条件

PDA在两种情况下停机：

danger

**确定PDA**和不确定PDA不等价。

能够精确找到状态转换发生的瞬间和时机，能够接收和识别语言。

danger

**确定PDA**和不确定PDA不等价。

扫描过程中，不能确定状态发生转换的瞬间和时机，没有确定位置进行转换，所以是不确定的。

对于不确定的 PDA 只需要把可能的情况包含进去即可，不用考虑确定化。

上下文无关文法 $G=(\Sigma, V, S,P)$ 是 CNF，若 G 的每个产生式形式为：

A→BC A，B，C∈V

A→a A∈V，a∈∑

S→ε 且 S 不出现在产生式的右边

则 G 是 Chomsky 范式 (CNF)。

上下文无关文法 $G=(\Sigma, V, S,P)$ 是 GNF，若 G 的每个产生式形式为：

A\rarr bW

其中： $b\in∑, W\in V, S\rarr \epsilon 且 S 不出现在产生式的右边$ 。（即要消除左递归）

可以由 GNF 产生 PDA。