有限オートマトンより強力で、決定論的プッシュ ダウン オートマトンより強力でないものはありますか?
1031 次
1 に答える
4
もちろん。UDPDA を 1 つのスタックシンボルのみを使用する DPDA と定義しましょう。つまり、スタックのアルファベットは単項です。そのような機械は言語 L = {a^nb^n | n > 0}、しかし言語ではない P = {w$w^R | w は単純な回文の任意の文字列} です。スタックを使用しないことで、任意の正規言語を認識できます。したがって、L(DFA) は L(UDPDA) のサブセットであり、L(DPDA) のサブセットです。
これよりもはるかにエキゾチックな、他の多くの種類のオートマトンを定義できますが、これも法案に適合する可能性があります。たとえば、プッシュダウン オートマトンほど強力でも劣らない最小ヒープ オートマトンを定義しました。それらについては、cs.stackexchange.com または Google の「min heap automata」で検索してください。
于 2012-04-02T20:53:44.473 に答える