确定下推自动机, 在自动机理论中, 英語, deterministic, pushdown, automaton, 縮寫, dpda, 是可以使用了持有数据的栈的确定有限状态自动机, 术语, 下推, 来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作, 术语, 当前指称识别确定上下文无关语言的抽象计算设备, 是减弱版本的下推自动机, 定义, 编辑一个下推自动机, 可以定义为一个, 元组, displaystyle, sigma, gamma, delta, 这里的, displaystyle, 是状态的有限. 在自动机理论中 确定下推自动机 英語 Deterministic pushdown automaton 縮寫 DPDA 是可以使用了持有数据的栈的确定有限状态自动机 术语 下推 来自原型机械自动机物理上接触穿孔卡片来阅读其内容的下推动作 术语 确定下推自动机 当前指称识别确定上下文无关语言的抽象计算设备 确定下推自动机是减弱版本的下推自动机 定义 编辑一个下推自动机 PDA M 可以定义为一个 7 元组 M Q S G q 0 Z 0 A d displaystyle M Q Sigma Gamma q 0 Z 0 A delta 这里的 Q displaystyle Q 是状态的有限集合 S displaystyle Sigma 是输入字母表的有限集合 G displaystyle Gamma 是栈字母表的有限集合 q 0 displaystyle q 0 是开始状态 是 Q displaystyle Q 的元素 Z 0 displaystyle Z 0 是初始栈符号 是 G displaystyle Gamma 的元素 A displaystyle A 是最终状态的集合 是 Q displaystyle Q 的子集 d displaystyle delta 是有限转移 transition 关系 Q S ϵ G P Q G displaystyle Q times Sigma cup left epsilon right times Gamma longrightarrow mathcal P Q times Gamma M 是确定的 如果它满足下列两个条件 对于任何 q Q a S ϵ X G displaystyle q in Q a in Sigma cup left epsilon right X in Gamma 集合 d q a X displaystyle delta q a X 有最多一个元素 对于任何 q Q X G displaystyle q in Q X in Gamma 如果 d q ϵ X displaystyle delta q epsilon X not varnothing 则 d q a X displaystyle delta q a X varnothing 对于所有 a S displaystyle a in Sigma 有两种可能的接受标准 空栈 接受和 最终状态 接受 对于确定下推自动机这两种接受是不等价的 尽管对于非确定下推自动机是等价的 被空栈接受的语言是被最终状态接受的语言 同时满足没有在语言中的串是在语言中的其他串的前缀 性质 编辑傑霍 賽尼澤格 英语 Geraud Senizergues 证明了确定 PDA 的等价问题 即给定两个确定 PDA A 和 B L A L B 吗 是可决定的 对非确定 PDA 这个问题是不可决定的 取自 https zh wikipedia org w index php title 确定下推自动机 amp oldid 75478588, 维基百科,wiki,书籍,书籍,图书馆,