state-machine - 比 DFA 更强大，但不如 DPDA

Question

有什么东西比有限自动机更强大，但比确定性下推自动机更弱？

Answer 1

当然。让我们将 UDPDA 定义为仅使用一个堆栈符号的 DPDA；即，堆栈字母表是一元的。这样的机器可以识别语言 L = {a^nb^n | n > 0}，但不是语言 P = {w$w^R | w 是简单回文的任意字符串}。它可以通过不使用堆栈来识别任何常规语言。所以 L(DFA) 是 L(UDPDA) 的子集，是 L(DPDA) 的子集。

您可以定义许多其他类型的自动机，比这更奇特，这也可能符合要求。例如，我定义了最小堆自动机，它的功能不比下推自动机强。您可以通过搜索 cs.stackexchange.com 或谷歌“最小堆自动机”来了解它们。