More powerful than a DFA but less than a DPDA [closed]

Question

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.

Closed 9 years ago.

Is there anything that is more powerful than a finite automaton but less powerful than a deterministic push down automaton?

Answer 1

Sure. Let us define a UDPDA to be a DPDA which uses only one stack symbol; i.e., the stack alphabet is unary. Such a machine can recognize the language L = {a^n b^n | n > 0}, but not the language P = {w$w^R | w is any string} of simple palindromes. It can recognize any regular language by not using the stack. So L(DFA) is a subset of L(UDPDA) is a subset of L(DPDA).

You can define many other kinds of automata, much more exotic than this, which might also fit the bill. For instance, I have defined min-heap automata which are neither more nor less powerful than pushdown automata. You can find out about them by searching cs.stackexchange.com, or Google "min heap automata".