<p>As pointed out in the comments, the power of such devices depends on the operations that they are allowed to perform on the ''register''. Here is a classic example of a class that captures all regular, but not all context-free languages.</p>

<p>If you restrict a PDA so that there is only one stack symbol, apart from the bottom-of-the-stack, the device is called a <strong>one-counter automaton</strong>.
I'm unsure what a standard reference is, but you can have a look, for instance, at <a href="http://link.springer.com/chapter/10.1007%2FBFb0039144" rel="nofollow noreferrer">this paper by Valiant and Paterson</a> in LNCS, vol. 2 (1973).</p>

<p>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).</p>

<p>Some proofs and additional information can be found <a href="https://cs.stackexchange.com/questions/7574/which-languages-are-recognized-by-one-counter-machines">here</a> and <a href="https://cs.stackexchange.com/questions/7286/is-determinism-non-determinism-for-one-counter-automata">here</a>.</p>

CC BY-SA 3.0
2014-02-19T16:45:32.433Z
2014-02-19T16:45:32.433Z
2017-04-13T12:48:30.830Z
dd1
<p>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).</p>

<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2011-06-02T19:30:06.753Z
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
CC BY-SA 3.0
2011-06-02T19:57:58.727Z
An infinite register and an arbitrary transition function trivially implies that *any* language is recognisable.
Jukka Suomela
CC BY-SA 3.0
2011-06-03T08:26:54.270Z
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
CC BY-SA 3.0
2011-06-03T09:32:20.670Z
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
CC BY-SA 3.0
2011-06-03T10:43:58.313Z
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
CC BY-SA 3.0
2011-06-03T10:48:08.907Z
Ah, you know what, I was making a very basic mistake. I actually have a "call-stack" in my model that I stupidly dismissed for some weird reason. Thanks Bart. (So a PDA + 1 separate register will still be equivalent to a PDA right? It should be since you can just store the register in the top of the stack.)
Rehno Lindeque
<reference-request><fl.formal-languages><automata-theory>
Are finite state automata with one register storage equivalent to push down automata?
Rehno Lindeque
# Are finite state automata with one register storage equivalent to push down automata?

(Asked by: username_0 on 2011-06-02)

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?

**Tags:** reference-request, fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: An infinite register and an arbitrary transition function trivially implies that *any* language is recognisable.  
> **username_0**: 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?  
> **username_3**: 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.  
> **username_0**: 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.  
> **username_0**: Ah, you know what, I was making a very basic mistake. I actually have a "call-stack" in my model that I stupidly dismissed for some weird reason. Thanks Bart. (So a PDA + 1 separate register will still be equivalent to a PDA right? It should be since you can just store the register in the top of the stack.)  

---

## 1 answers

### Answer by username_4 on 2014-02-19. Score: 2

As pointed out in the comments, the power of such devices depends on the operations that they are allowed to perform on the ''register''. Here is a classic example of a class that captures all regular, but not all context-free languages.

If you restrict a PDA so that there is only one stack symbol, apart from the bottom-of-the-stack, the device is called a **one-counter automaton**.
I'm unsure what a standard reference is, but you can have a look, for instance, at [this paper by Valiant and Paterson](http://link.springer.com/chapter/10.1007%2FBFb0039144) in LNCS, vol. 2 (1973).

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).

Some proofs and additional information can be found [here](https://cs.stackexchange.com/questions/7574/which-languages-are-recognized-by-one-counter-machines) and [here](https://cs.stackexchange.com/questions/7286/is-determinism-non-determinism-for-one-counter-automata).


---

