下推自动机

维基百科，自由的百科全书

下推自动机﹙PDA﹚是自动机理论中定义的一种抽象的计算模型。下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。下推自动机可以形象的理解为，藉由加上讀取一個容量無限堆疊的能力，擴充一個能做 $ε$ -轉移的非確定有限狀態自動機。

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

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

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

[编辑] 形式定义

下推自动机 $M$ 是如下的一个七元组 $(Q,Σ,Γ,δ, q 0, Z 0, F)$ ，其中：

$Q$ 是一个有穷状态集合；
$Σ$ 是一个字母表，称为输入字母表。
$Γ$ 是一个字母表，称为栈字母表。
$q 0$ 属于 $Q$ ，是初始状态。
$Z 0$ 属于 $Γ$ ，是一个特殊的栈符号，称为栈起始符号。
$F$ 包含于 $Q$ ，是终结状态集合。
$\delta : Q \times (\Sigma \cup \{\epsilon\}) \times \Gamma \rightarrow Q \times \Gamma^{*}$ 是 $M$ 的动作函数。

[编辑] 例子

如同 $0 n 1 n$ 这样的context-free的字符串，就是下推自动机应用的领域： ${0 n 1 n | n > 0}$ .我们让 $M 1 = {Q, V, T, s, q 1, F}$

 $Q = {q 1, q 2, q 3, q 4}$ 
 $V = {0,1}$ 
 $T = {0,$}$ 
 $F = {q 1, q 4}$

转换函数s如下表

input:  $0 | 1 | ε |$  
Stack:  
 
 $q 2 :{(q 2,0)}{(q 3,ε)}$ 
 $q 3 :{(q 3,ε)}{(q 4,ε)}$  
 $q 4 :$

下面是状态图：

     e,e->$       0,e->0
->q1----------->q2---
                 |A__|
                 |
                 |1,0->e
                 V  
  q4<------------q3--
        e,$->e    A__|1,0->e
q1,q4为中止状态。
（引自计算理论导引，Michael Sipser）

[编辑] 历史

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

[编辑] 参考书目

《自动机理论、语言和计算导引》，John E. Hopcroft，Jeffery D. Ullman，徐美瑞译，洪加威校，科学出版社，1986年

来自“http://zh.wikipedia.org../../../%E4%B8%8B/%E6%8E%A8/%E8%87%AA/%E4%B8%8B%E6%8E%A8%E8%87%AA%E5%8A%A8%E6%9C%BA.html”

页面分类: 编译原理 | 形式语言 | 自动机