比DFA更強大但小於DPDA

Question

有什麼比有限自動機更強大但比確定性下推自動機更強大？

Answer 1

當然。讓我們定義一個UDPDA爲只使用一個堆棧符號的DPDA;即堆棧字母表是一元的。這樣的機器可以識別語言L = {a^n b^n | n> 0}，但不是語言P = {w $ w^R | w是簡單迴文的任何字符串。它可以通過不使用堆棧來識別任何常規語言。所以L（DFA）是L的一個子集（UDPDA）是L（DPDA）的一個子集。

您可以定義許多其他種類的自動機，比這更奇特，這也可能適合賬單。例如，我已經定義了min-heap自動機，它既不比下推自動機強大也不低於。您可以通過搜索cs.stackexchange.com或Google「min heap automata」來了解它們。