3
$\begingroup$

Lets define a counting PDA as equivalent to a PDA except that the transition relation can use the stack size.

Formally, let's define the transition relation as $\Delta:Q\times (\Sigma \cup \{ \epsilon \}) \times (\Gamma\cup\{\epsilon\})\times \mathbb{N} \to P(Q\times (\Gamma\cup \{ \epsilon \}) )$

Meaning that $(q,\beta) \in \Delta(r,\sigma, \alpha, n)$ means that when the automaton is in state r reading the symbol $\sigma$, the head of the stack contains $\alpha$ and we have n items in the stack, then we can remove $\alpha$ and insert $\beta$ and transition to q.

My question is whether the family of automata created by this definition of a counting PDA is equivalent to family of PDAs.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

Nope. A counting PDA is more powerful than a PDA... even more powerful than a Turing machine. It can recognize undecidable languages.

Proof: Let $L \subseteq \{1\}^*$ be an undecidable unary language. It's easy to build a PDA that pushes one symbol on its stack per symbol on the input tape. Then the height of the stack fully encodes the input word. Thus its final transition can in one step decide whether the input word is in $L$, by "encoding" $L$ fully into the transition relation $\Delta$.

In retrospect, this is perhaps not too surprising. A counting PDA is not physically realizable. A PDA has a finite description. A Turing machine has a finite description. A counting PDA does not. Thus, it's not too surprising that it might be more powerful.

Or, to put it another way, because they have a finite description, there are only countably many PDA's and only countably many Turing machines; but there are uncountably many counting PDA's. As a result, it's not surprising that there exists a language accepted by a counting PDA that isn't accepted by any PDA (or any Turing machine) -- for this not to be the case, there would have to be some enormous equivalence among counting PDAs that map the uncountably many counting PDAs to only countably many languages.

How do we know there exists an undecidable unary language? Well, let $L_2 \subset \{0,1\}^*$ be any ordinary undecidable language in binary. Now map each word $x \in L_2$ to its unary encoding; this gives you a unary language $L_1$. Then $L_1$ must be undecidable too (because the mapping is computable). For instance, the binary word $110$ maps to the unary word $1^6$, since $110$ is the binary representation of 6. (Strictly speaking, we must adjust the encoding slightly, to make sure that $110$ and $0110$ don't map to the same thing, but that's easy to fix up.)

Improve this answer
$\endgroup$
2
  • $\begingroup$ What happens if you impose some uniformity constraint? What if the transition relation must be, say, regular? If it is finite, then of course no power is gained. On the other hand, your argument shows that the counting PDA should be at least as powerful as the transition relation. $\endgroup$
    – Thom Smith
    May 22, 2018 at 17:50
  • $\begingroup$ @ThomSmith, I don't know. If you're interested and you've thought about it, I'd suggest posting a new question using the 'Ask Question' button. That said: I'm not entirely sure what it would mean for the transition relation to be regular (since one of its arguments is a natural number), so if you want to ask about that, please specify what that means. Do show us what you've come up with so far. I think it's more reasonable to ask about a specific case (e.g., the transition relation must be regular) rather than leaving it open what kind of uniformity constraint you might be thinking of. $\endgroup$
    – D.W. ♦
    May 22, 2018 at 20:03

Your Answer

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

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