woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

维基百科----下推自动机

综述

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

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

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

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

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

[编辑] 形式定义

PDA 形式定义为 6-元组:

clip_image001这里的

  • clip_image002状态的有限集合
  • clip_image003是输入字母表的有限集合
  • clip_image004字母表的有限集合
  • clip_image005: clip_image006转移函数
  • q0 是“开始状态”
  • clip_image007是“接受状态”的集合
  • clip_image008
  • clip_image009

计算定义 1

对于任何 PDA clip_image001,计算路径是一个有序的(n+1)-元组 clip_image010,这里的 clip_image011,它满足如下条件:

(i) clip_image012对于 i = 0, 1, 2,......, n-1,

这里的 clip_image013

(ii) clip_image014使得

clip_image015

在直觉上,PDA 在计算过程中任何一点上都面对着多种可能性,从栈顶读一个符号并把它替代为另一个符号,从栈顶读一个符号并删除它而不替换,不从栈顶读任何符号但压入另一个符号进去,或什么都不做。所有这些都同时由等式 clip_image016clip_image017来支配。clip_image018 是紧接在第 i+1 次转移移动之前的栈内容,而 clip_image019是要从栈顶去除的符号。clip_image020 是紧接在第 i+1 次转移移动之后栈内容,而 clip_image021是在第 i+1 次转移移动期间要增加到栈上的符号。

clip_image019clip_image021二者都可以 clip_image022

如果 clip_image023clip_image024,则 PDA 从栈读一个符号并把它替代为另一个符号。

如果 clip_image023clip_image025,则 PDA 从栈读一个符号并删除它而不替换。

如果 clip_image026clip_image024,则 PDA 简单的增加一个符号到栈上。

如果 clip_image026clip_image025,则 PDA 保持栈不变动。

注意当 n=0 时,计算路径就是单元素集合 clip_image027

计算定义 2

对于任何输入 clip_image028M 接受 w,如果存在计算路径 clip_image029和有限序列 clip_image030,使得

(i) 对于每个 i = 0, 1, 2,...mclip_image031 都在计算路径上。就是说

clip_image032这里的 clip_image033使得 clip_image034

(ii) clip_image035对于每个 i = 0, 1, 2,...m-1

这里的 clip_image036clip_image037定义同于计算定义 1

(iii) clip_image038,如果 clip_image039

这里的 clip_image040clip_image041定义同于计算定义 1

(iv) clip_image042clip_image043

注意上述定义不提供测试空栈的机制。要这么做你需要在所有计算开始前在栈上写一个特殊符号,使得 PDA 可以在检测到这个符号的时候有效的识别出栈已经空了。形式的说,实现它可通过介入转移 clip_image044这里的 $ 是特殊符号。

[编辑] 例子

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

clip_image046

  • clip_image047
  • clip_image048
  • clip_image049
  • clip_image050
  • clip_image051
  • clip_image052
  • clip_image053
  • clip_image054
  • clip_image055
  • clip_image056对于任何其他状态、输入和栈符号的值。

[编辑] 理解计算过程

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

(a) 输入字符串 = 0011

(i) δ(q1, ε, ε) clip_image057(q2, $) 来表示 (q2, $) clip_image058δ(q1, ε, ε)

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

设置 r0 = q2

(ii) δ(r0, 0, ε) = δ(q2, 0, ε) clip_image057(q2, 0)

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

设置 r1 = q2

(iii) δ(r1, 0, ε) = δ(q2, 0, ε) clip_image057(q2, 0)

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

设置 r2 = q2

(iv) δ(r2, 1, 0) = δ(q2, 1, 0) clip_image057(q3, ε)

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

设置 r3 = q3

(v) δ(r3, 1, 0) = δ(q3, 1, 0) clip_image057(q3, ε)

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

(vi) δ(q3, ε, $) clip_image057(q4, ε)

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

设置 r4 = q4

因为 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) = clip_image059

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

(c) 输入字符串 = ε

设置 r0 = q1, r1 = q1

δ(r0, ε, ε) clip_image057(q1, ε)

因为 q1 是接受状态,ε 被接受。

[编辑] 广义下推自动机(GPDA)

GPDA 是在一个步骤内写入整个字符串到栈上或从栈上去除整个字符串的 PDA

GPDA 形式定义为 6-元组 clip_image001

这里的 Q, clip_image060, clip_image061, q0 F 的定义同于 PDA

clip_image005: clip_image062是转移函数。

GPDA 的计算规则同于 PDA,除了 ai+1 bi+1 现在是字符串而不是符号之外。

GPDA PDA 是等价的,如果一个语言可被一个 PDA 识别,它也可被一个 GPDA 识别,反之亦然。

可以使用下列模拟公式化对 GPDA PDA 的等价性的一个分析式证明:

δ(q1, w, x1x2...xm) clip_image063(q2, y1y2...yn) GPDA 的转移。

这里的 q1, q2 clip_image058Q, w clip_image064, x1x2...xm clip_image065, mclip_image0660, y1y2...yn clip_image065, nclip_image0660

构造 PDA 的下列转移:

δ'(q1, w, x1) clip_image063(p1, ε)

δ'(p1, ε, x2) clip_image063(p2, ε)

clip_image067

δ'(pm-1, ε, xm) clip_image063(pm, ε)

δ'(pm, ε, ε ) clip_image063(pm+1, yn)

δ'(pm+1, ε, ε ) clip_image063(pm+2, yn-1)

clip_image067

δ'(pm+n-1, ε, ε ) clip_image063(q2, y1)

[编辑] 参见

[编辑] 外部链接

[编辑] 参考书目

  • 《自动机理论、语言和计算导引》,John E. HopcroftJeffery D. Ullman,徐美瑞译,洪加威校,科学出版社,1986
  • Michael Sipser1997).Introduction to the Theory of ComputationPWS PublishingISBN 0-534-94728-X  Section 2.2: Pushdown Automata, pp.101114.

自动机理论: 形式语言和形式文法

乔姆斯基层级

文法

语言

极小自动机

类型 0

无限制

递归可枚举

图灵机

n/a

(无公用名)

递归

判定器

类型 1

上下文有关

上下文有关

线性有界

n/a

附标

附标

嵌套堆栈

n/a

树-邻接

适度上下文有关

嵌入下推

类型 2

上下文无关

上下文无关

非确定下推

n/a

确定上下文无关

确定上下文无关

确定下推

类型 3

正则

正则

有限

每个语言或文法范畴都是其直接上面的范畴的真子集

取自"http://zh.wikipedia.org/w/index.php?title=%E4%B8%8B%E6%8E%A8%E8%87%AA%E5%8A%A8%E6%9C%BA&variant=zh-cn"

 

posted on 2008-12-30 10:50 肥仔 阅读(1070) 评论(0)  编辑 收藏 引用 所属分类: 状态机 & 自动机 & 形式语言


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理