Mini wiki
下推自动机
编辑
在
自动机理论
中,下推自动机是使用了包含数据的
堆栈
的
自动机
。
1
相关
上下文无关语言
是可以用上下文无关文法定义的形式语言。所有上下文无关语言的集合同一于
下推自动机
所接受的语言的集合。
嵌入下推自动机
或 EPDA 是分析树-邻接文法的计算模型。除了不再使用堆栈来存储符号之外,它类似于分析上下文无关文法的
下推自动机
。它有存储符号的重复堆栈组成的一个栈,这给予了 TAG 在上下文无关文法和上下文有关文法之间的复杂度,或者说是适度上下文有关文法的子集。