檢視下推自动机的原始碼

{| class="wikitable" align="right"

|-

| style="background: #008080" align= center|  '''<big>下推自动机</big> '''

|-

| 
[[File:202001011419451682345678.png|缩略图|居中|[https://img-blog.csdnimg.cn/20200101141945168.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1aWh1aXNk,size_16,color_FFFFFF,t_70原图链接][https://blog.csdn.net/huihuisd/article/details/103792161 来自 搜狗 的图片]]]
	
|-	

| style="background: #008080" align= center|

|-

| align= light|

|} 
在自动机理论中，下推自动机（Pushdown automaton）是使用了包含数据的栈的有限自动机。

=='''目录'''==

'''综述'''

'''形式定义'''

'''例子'''

'''广义下推自动机(GPDA)'''

=='''综述'''==

下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。下推自动机可以形象的理解为，借由加上读取一个容量无限栈的能力，扩充一个能做-转移的非确定有限状态[[自动机]]。

下推自动机存在“确定”与“非确定”两种形式，两者并不等价。（对有限状态自动机两者是等价的）

每一个下推自动机都接受一个形式语言。被“非确定下推自动机”接受的语言是上下文无关语言。

如果我们把下推自动机扩展，允许一个有限状态自动机存取两个栈，我们得到一个能力更强的自动机，这个自动机与图灵机等价。

下推自动机作为一个形式系统最早于1961年出现在 Oettinger 的论文中。它与上下文无关文法的等价性是由乔姆斯基于1962年发现的。

=='''形式定义'''==

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 可以在检测到这个符号的时候有效的识别出栈已经空了。形式的说，实现它可通过介入转移 这里的 $ 是[[特殊符号]]。

'''3例子'''

下面是识别语言  的 PDA 的形式描述：

对于任何其他状态、输入和栈符号的值。

=='''理解计算过程'''==

下面展示上述 PDA 如何计算不同的输入字符串。

(a) 输入字符串 = 0011

(i) 写 (q1, , )  (q2, $) 来表示 (q2, $)  (q1, , )

s0 = , s1 = $, t = , a = , b = $

设置 r0 = q2

(ii) (r0, 0, ) = (q2, 0, )  (q2, 0)

s1 = $, a = , t = $, b = 0, s2 = 0$

设置 r1 = q2

(iii) (r1, 0, ) = (q2, 0, )  (q2, 0)

s2 = 0$, a = , t = 0$, b = 0, s3 = 00$

设置 r2 = q2

(iv) (r2, 1, 0) = (q2, 1, 0)  (q3, )

s3 = 00$, a = 0, t = 0$, b = , s4 = 0$

设置 r3 = q3<ref>

(v) (r3, 1, 0) = (q3, 1, 0)  (q3, )

s4 = 0$, a = 0, t = $, b = , s5 = $

(vi) (q3, , $)  (q4, )

s5 = $, a = $, t = , b = , s6 = 

设置 r4 = q4<ref>[https://weixin.sogou.com/weixin?query=1884年&ie=utf8&type=2&sourceid=weixinvr   下推自动机],搜狗, 2018-05-13</ref> 

因为 q4 是接受状态，0011 被接受。

作为总结，计算路径 = (q1, q2, q2, q2, q3, q3, q4)

而 (r0, r1, r2, r3, r4) = (q2, q2, q2, q3, q4)

(b) 输入字符串 = 001

计算移动 (i), (ii), (iii), (iv) 将必定同于情况 (a)，否则，PDA 在到达 (v) 之前就已经进入[[死胡同]]。

(v) (r3, , a) = (q3, , a)

因为 s4 = 0$，要么 a =  要么 a = 0

在任何一种情况下，(q3, , a) = 

因此计算在 r3 = q3 进入死胡同，这不是接受状态。所以 001 被拒绝。

(c) 输入字符串 = 

设置 r0 = q1, r1 = q1

(r0, , )  (q1, )

因为 q1 是接受状态， 被接受。

4广义下推自动机(GPDA)
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)

=='''参考资料'''==
{{Reflist}}