非确定性下推自动机

非确定性下推自动机与 NFA 非常相似。我们将讨论一些接受 NPDA 的 CFG。

接受确定性 PDA 的 CFG 也接受非确定性 PDA。同样，有些 CFG 只能被 NPDA 接受，而不能被 DPDA 接受。因此，NPDA 比 DPDA 更强大。

示例

为回文串设计 PDA。

解决方案

假设语言包含字符串 L = {aba, aa, bb, bab, bbabb, aabaa, ......]。该字符串可以是奇数回文或偶数回文。构造 PDA 的逻辑是，我们将一个符号压入堆栈，直到字符串的一半，然后我们将读取每个符号，然后执行弹出操作。我们将比较以查看弹出的符号是否与读取的符号相似。无论我们是否到达输入的末尾，我们都希望堆栈为空。

此 PDA 是非确定性 PDA，因为找到给定字符串的中间位置并从左侧读取字符串并从右侧（反向）匹配会导致非确定性移动。这是 ID。

abaaba 的模拟