language-agnostic - 确定性有限自动机与确定性下推自动机

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，则保持此状态。
     • 如果弹出的值为 $，则进入终端不接受状态。
   • 如果我们读取字符串的结尾，则从堆栈中弹出顶部的值
     • 如果弹出的值为$，则进入接受状态
     • 如果弹出的值为A，则进入终端不接受状态。
   • 如果我们从字符串中读取任何其他内容，则进入终端不接受状态。

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