下推自动机
Cnic.org,开放的网络天书！
下推自动机﹙PDA﹚是自动机理论中定义的一种抽象的计算模型。下推自动机比有限状态自动机复杂：除了有限状态组成部分外，还包括一个长度不受限制的栈；下推自动机的状态迁移不但要参考有限状态部分，也要参照栈当前的状态；状态迁移不但包括有限状态的变迁，还包括一个栈的出栈或入栈过程。下推自动机可以形象的理解为，把有限状态自动机扩展使之可以存取一个栈。
下推自动机存在确定与非确定两种形式，两者并不等价。﹙对有限状态自动机两者是等价的﹚
每一个下推自动机都接受一个形式语言。被非确定下推自动机接受的语言是上下文无关语言。
如果我们把下推自动机扩展，允许一个有限状态自动机存取两个栈，我们得到一个能力更强的自动机，这个自动机与图灵机等价。
目录 |
[编辑]
形式定义
下推自动机 M 是如下的一个七元组 ( Q, Σ, Γ, δ, q0, Z0, F ) ，其中：
- Q 是一个有穷状态集合；
- Σ 是一个字母表，称为输入字母表。
- Γ 是一个字母表，称为栈字母表。
- q0 属于 Q ，是初始状态。
- Z0 属于 Γ ，是一个特殊的栈符号，称为栈起始符号。
- F 包含于 Q ，是终结状态集合。
- δ : Q×(Σ∪{ε})×Γ -> Q×Γ* 是 M 的动作函数。
[编辑]
例子
[编辑]
历史
下推自动机作为一个形式系统最早于1961年出现在 Oettinger 的论文中。它与上下文无关文法的等价性是由乔姆斯基于1962年发现的。
[编辑]
参考书目
- 《自动机理论、语言和计算导引》，John E. Hopcroft，Jeffery D. Ullman，徐美瑞译，洪加威校，科学出版社，1986年
