# Are finite state automata with one register storage equivalent to push down automata?

This is a very simple question, but I couldn't find a reference and I just wanted to check my facts. I was looking for a state machine similar to pushdown automata but where the stack is restricted to one element (i.e. a register).

It occurred to me that if the register has an infinite alphabet (of possible values) it will basically be equivalent to a PDA. Every configuration of the stack could be represented by a single element of the register's alphabet. (E.g. let's say that the register's alphabet is the set of natural numbers). Is this correct?

Furthermore, a DFSM is equivalent in strength to a NFSM. However, I assume that (DFSM + 1 register) would not be equivalent to a (NFSM + 1 register) since DPDA and NPDA are not equivalent?

• I think the problem with the infinite alphabet depends on how you operate on it. Even in a turing machine the size transition function depends on the size of the alphabet. In this case the FSM will need an infinite transition function, which contradicts the fact that it is "finite" after all. – Mohammad Alaggan Jun 2 '11 at 19:30
• An infinite register and an arbitrary transition function trivially implies that any language is recognisable. – Jukka Suomela Jun 2 '11 at 19:57
• Ah, thanks I see. The algorithm I'm developing does NOT have an infinite transition function. I assume that puts its computational strength somewhere between FSA and PDA? – Rehno Lindeque Jun 3 '11 at 8:26
• If it does not have an infinite transition function, you can assume a finite alphabet, because such a transition function is only able to choose among a finite set of strings to write to the register. Such a machine can be simulated by a FSA, so it is not stronger, if I don't misunderstand something. – Bart Jun 3 '11 at 9:32
• Mmm... You might be right about that, I have to think about it. In the model I'm trying to formalize a state can return to a previous state with a new value in the register. Then the previous state makes a decision based on this value. – Rehno Lindeque Jun 3 '11 at 10:43

For such a device, the set of all possible stack configurations is infinite (non-negative integers), but when it comes to operations on the stack, you can only increment and decrement the value by $1$ and test for $0$. This class of automata is strictly less powerful than the class of all pushdown automata; restricting it further with determinism results in an even weaker class. Also note that if you go for two counters instead of one, then even with deterministic machines you reach undecidability (even for the word problem, i.e., given a word, decide whether it is accepted).