确定性有限自动机与确定性下推自动机

Question

我想知道是否有人可以对这两个术语之间的关系进行简单的解释，因为我对术语感到非常困惑。

Answer 1

确定性下推自动机(DPDA) 是确定性有限自动机(DFA)，它也可以访问堆栈，堆栈是后进先出 (LIFO) 数据结构。

访问某种形式的内存允许 DPDA 比 DFA 识别更多种类的字符串。例如，给定一种带有符号 A 和 B 的语言，可以构造一个 DFA 来识别 AB、AABB、AAABBB，但是不能构造一个 DFA 来识别所有 n 的 A^nB^n，而使用 DPDA 很容易做到其工作原理如下：

1. 进入开始状态。
2. 推$入堆栈。
3. 从字符串中读取字母。
   • 如果是 B，则进入终端非接受状态。
   • 如果是 A，则将 A 压入堆栈，然后转到状态 4。
4. 从字符串中读取一个字母
   • 如果 A，则将 A 压入堆栈并保持此状态
   • 如果为 B，则从堆栈中弹出顶部值。
     
     • 如果弹出的值是 A，则转到状态 5。
     • 如果弹出的值为 $，则进入终端非接受状态。
5. 从字符串中读取一个字母
   • 如果为 B，则从堆栈中弹出顶部值。
     
     • 如果弹出的值为 A，则保持此状态。
     • 如果弹出的值为 $，则进入终端非接受状态。
   • 如果我们读取字符串的结尾，则从堆栈中弹出顶部值
     • 如果弹出的值为$，则进入accept状态
     • 如果弹出的值为 A，则进入终端非接受状态。
   • 如果我们从字符串中读取任何其他内容，则进入终端非接受状态。

PDA 识别上下文无关语言，而 DPDA 仅识别上下文无关语言的确定性子集。就它们可以识别的语言数量而言，它们比 DFA 更强大，但不如图灵机强大