1
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ 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. $\endgroup$
    – Mohammad Alaggan
    Commented Jun 2, 2011 at 19:30
  • 2
    $\begingroup$ An infinite register and an arbitrary transition function trivially implies that any language is recognisable. $\endgroup$
    – Jukka Suomela
    Commented Jun 2, 2011 at 19:57
  • $\begingroup$ 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? $\endgroup$
    – Rehno Lindeque
    Commented Jun 3, 2011 at 8:26
  • $\begingroup$ 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. $\endgroup$
    – Bart
    Commented Jun 3, 2011 at 9:32
  • $\begingroup$ 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. $\endgroup$
    – Rehno Lindeque
    Commented Jun 3, 2011 at 10:43

1 Answer 1

Reset to default
2
$\begingroup$

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 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 and here.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.