在计算理论中解释非确定性下推自动机。

非确定性下推自动机 (NPDA) 类似于有限自动机 (FA)，但它还有一个堆栈内存，可以在其中存储任意数量的信息。

读/写堆栈内存的工作方式是后进先出 (LIFO)。

我们可以用堆栈做什么？

弹出操作读取顶部符号并将其从堆栈中删除；压入操作将指定的符号写入堆栈顶部，例如 push(X) 表示将 X 放入堆栈顶部；nop 操作对堆栈不做任何操作。

堆栈符号与输入带上使用的“语言”字母不同。

我们从以下开始：

  • 堆栈上只有初始堆栈符号（堆栈上没有其他内容！）处于控制自动机的起始状态。

  • 在每一步中，状态、输入元素和堆栈中的顶部符号决定下一步（转换）。

一个转换步骤包括以下内容：

  • 更改状态（如 FA）。

  • 从输入带上读取符号并移动到下一个右侧符号（如 FA）。

  • 更改堆栈（将符号压入堆栈/从堆栈弹出符号/堆栈无变化）。

转换步骤由转换函数正式定义（通常以转换指令的形式）。

NPDA 可以描述如下：

  • 一个有限的状态集 Q（和起始状态以及接受/最终状态集）。

  • 一个有限的输入字母表集 ∑。

  • 一个有限的堆栈字母表集 Γ（和初始堆栈符号 $）。

  • 一组有限的转换指令（或转换函数 T）。

T : Q × ∑ ∪ {∧} × Γ → Γ* × Q

或者它可以用下图所示的“转换”图表示：

更新于：2021年6月15日

9K+ 次浏览

启动你的职业生涯

完成课程获得认证

开始学习
广告