PDA 形式定义为 6-元组:
这里的
- 是状态的有限集合
- 是输入字母表的有限集合
- 是栈字母表的有限集合
- : 是转移函数
- 是“开始状态”
- 是“接受状态”的集合
计算定义 1
对于任何 PDA ,计算路径是一个有序的(n+1)-元组 ,这里的 ,它满足如下条件:
(i) 对于 i = 0, 1, 2,......, n-1,
- 这里的
(ii) 使得
在直觉上,PDA 在计算过程中任何一点上都面对着多种可能性,从栈顶读一个符号并把它替代为另一个符号,从栈顶读一个符号并删除它而不替换,不从栈顶读任何符号但压入另一个符号进去,或什么都不做。所有这些都同时由等式 和 来支配。 是紧接在第 i+1 次转移移动之前的栈内容,而 是要从栈顶去除的符号。 是紧接在第 i+1 次转移移动之后栈内容,而 是在第 i+1 次转移移动期间要增加到栈上的符号。
和 二者都可以 。
如果 而 ,则 PDA 从栈读一个符号并把它替代为另一个符号。
如果 而 ,则 PDA 从栈读一个符号并删除它而不替换。
如果 而 ,则 PDA 简单的增加一个符号到栈上。
如果 而 ,则 PDA 保持栈不变动。
注意当 n=0 时,计算路径就是单元素集合 。
计算定义 2
对于任何输入 ,M 接受 w,如果存在计算路径 和有限序列 ,使得
(i) 对于每个 i = 0, 1, 2,...m, 都在计算路径上。就是说
- 这里的 使得
(ii) 对于每个 i = 0, 1, 2,...m-1。
- 这里的 和 定义同于计算定义 1。
(iii) ,如果
- 这里的 和 定义同于计算定义 1。
(iv) 且
注意上述定义不提供测试空栈的机制。要这么做你需要在所有计算开始前在栈上写一个特殊符号,使得 PDA 可以在检测到这个符号的时候有效的识别出栈已经空了。形式的说,实现它可通过介入转移 这里的 $ 是特殊符号。
GPDA 是在一个步骤内写入整个字符串到栈上或从栈上去除整个字符串的 PDA。
GPDA 形式定义为 6-元组
- 这里的 Q, , , q0 和 F 的定义同于 PDA。
- : 是转移函数。
GPDA 的计算规则同于 PDA,除了 ai+1 和 bi+1 现在是字符串而不是符号之外。
GPDA 和 PDA 是等价的,如果一个语言可被一个 PDA 识别,它也可被一个 GPDA 识别,反之亦然。
可以使用下列模拟公式化对 GPDA 和 PDA 的等价性的一个分析式证明:
设 (q1, w, x1x2...xm) (q2, y1y2...yn) 是 GPDA 的转移。
这里的 q1, q2 Q, w , x1x2...xm , m0, y1y2...yn , n0。
构造 PDA 的下列转移:
- (q1, w, x1) (p1, )
- (p1, , x2) (p2, )
- (pm-1, , xm) (pm, )
- (pm, , ) (pm+1, yn)
- (pm+1, , ) (pm+2, yn-1)
- (pm+n-1, , ) (q2, y1)