DFAよりもパワフルで、DPDAよりも強力です

Question

有限オートマトンよりも強力ですが、確定的プッシュダウンオートマトンより強力ではないものはありますか？

Answer 1

UDPDAを1つのスタックシンボルだけを使用するDPDAと定義しましょう。すなわち、スタックアルファベットは単項式である。このようなマシンは、言語L = {a^n b^n | n> 0}であるが、言語P = {w $ w^R | wは単純な回文の任意の文字列}です。スタックを使用しないことで、通常の言語を認識できます。したがって、L（DFA）はL（UDPDA）のサブセットであり、L（DPDA）のサブセットである。

多くの他の種類のオートマトンを定義することができます。これは、これよりはるかにエキゾチックであり、法案にも適合します。たとえば、プッシュダウンオートマトンよりも強力でもなく強力でもないミニヒープオートマトンを定義しました。あなたはcs.stackexchange.comやGoogleの "min heap automata"を検索することでそれらについて知ることができます。