区分TOC中的DPDA和NPDA？

与有限自动机(FA)类似，下推自动机(PDA)可以是确定性的或非确定性的。

确定性下推自动机(DPDA)永远没有下一步的选择 -

与确定性有限自动机(DFA)相比，它对每个状态、输入字符和堆栈字符的组合都有可能的输出。

我们需要小心处理每个状态和堆栈字符的组合。对于空符号∧或输入符号，只允许一个事务。或者根本没有事务。

示例

非确定性下推自动机(NPDA)可以包含以下指令，但DPDA不能包含这些指令。

  • 例1 - (0, a, $,push(Y), 0); (0, a, $,pop, 1)

  • 例2 - (0, ∧, $, pop, 3); (0, b, $, nop, 2)

示例

考虑偶数长度回文 - L = {wwR | w ∈ {a, b}+}

状态转换图如下：

这是一个NPDA的例子，因为从状态0开始，它会分支，或者加载另一个字母，或者尝试删除字母。这只能非确定性地完成。

DPDA需要知道何时开始从堆栈中删除字母。因此，NPDA可以识别偶数回文语言，但DPDA不能。

DPDA识别正则语言以及一些非正则语言，但并非所有上下文无关语言。

下图描述了DPDA和NPDA在识别正则语言和上下文无关文法方面的区别：

更新于：2021年6月15日

5K+ 次浏览

启动你的职业生涯

通过完成课程获得认证

开始
广告