4. 确定的下推自动机¶
4.1. 确定的下推自动机¶
我们知道，非确定性并不会给 DFA 带来真正的能力增强。 也就是说，每个 NFA 都有一个等价的 DFA。 因此，DFA 所识别的语言集合与 NFA 所识别的语言集合相同。
那么 PDA 呢？ 我们已经把非确定性的概念引入了 PDA（这样的机器称为 NPDA），并且已经证明每个 CFG 都有一个等价的 NPDA，反之亦然。 因此，NPDA 能够识别所有的 CFL。
但是，确定性与非确定性的 PDA 之间的区别又如何？ 非确定性是否给 PDA 带来了真正的能力增强？
