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

Question

我想知道是否有人可以给我一个简单的解释这两个术语之间的关系，因为我对术语很困惑。

Answer 1

确定性 Pushdown Automaton (DPDA) 是 Deterministic Finite Automaton (DFA) 也可以访问 Stack ，这是一种后进先出 (LIFO) 数据结构。

与 DFA 相比，DPDA 可以访问某种形式的内存，从而可以识别更多种类的字符串。例如，给定一种带有符号 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 识别 context-free languages , DPDAs 只识别上下文无关语言的确定性子集。就可识别的语言数量而言，它们比 DFA 更强大，但不如 Turing Machines 强大。