PDA

基本概念与形式定义

对于PDA而言，其对应的表达能力和上下文无关语法一致。相比于DFA来说，它具有一定“记忆”能力，能够记住以前输入的字符。

形式定义：不确定的下推自动机（NPDA）是一个七元组，其中，的定义和DFA一致
:即为其下推栈字母表的集合
:其下推栈的起始字符，
:转换函数，从到的映射
对于转换式


可以用以上的图形表示
若，则意味着栈顶被弹出

格局

下推自动机的瞬时工作状况，也可以用格局描述，是一个三元组，即，其中：
q:当前状态，
w:待输入的字符串，，当时，代表输入字符已经读完
a: 下推栈中的所有内容，，当时，代表下推栈已弹空
转换函数

可以用格局表示为：|——

构造PDA

构造PDA有两个核心，即其接收的方式。由于PDA的记忆性完全来自于栈的特性，因此，大部分的设计都是基于空栈标识的，即当栈弹空之后，就接收。
另外的一种接收方式是基于终态的，即设置一个终止状态，只要转移到终态之后，待输入的字符为空了，那么就接收
例1. 构造PDA，接收语言

另外，我们还可以给出一个定理，来证明空栈接受和终态接受的等价性

其主要思想就是，对于任意一个空栈接受的自动机，我们都可以将其空栈状态指向一个新的作为终结态。

上下文无关文法和下推自动机

由文法产生自动机

即，给定，G是一个上下文无关文法，则必然存在一个下推自动机接受
算法过程描述如下：
1) 将文法的起始符号S放入栈中
2) 重复以下步骤：
3) 如果栈顶是非终结符A，那么从A的生成式中随机选择一个，丢入栈中
4) 如果栈顶是终结符a，那么读入下一个符号，如果匹配，那么回到(2)，如果不匹配，那么这个非确定分支被拒绝
5) 如果栈空，且此时输入已经读完，那么接收这个字符串

形式定义如下：
设，其中：
，，，，
的定义如下：
- 如果，那么含有
- 对所有，