6
$\begingroup$

For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space.

But what about PDAs with $\epsilon$-transitions? Is the halting problem decidable for deterministic PDA's with $\epsilon$-transitions? Given such a DPDA $P$ and an input $x$, can we decide whether $P$ will halt on input $x$?

The stack may be infinitely large, so it seems like it might be much harder here to see if the PDA is in an infinite loop or not.

I don't think it's as easy as answered here for non-$\epsilon$ PDAs:

[For] DFAs or PDAs, the halting problem is decidable: the machine always halts because it halts when it reaches the end of its input, the input is finite and the machine consumes one character of input at every step.

Is the halting problem specific to Turing machines?)

The answer to my earlier question (Is a PDA's stack size linear bounded in input size?) also seems to point in a direction of a higher difficulty of proving this.

|cite|improve this question
$\endgroup$
  • $\begingroup$ On a specific input. Isn't that the "standard" halting problem? $\endgroup$ – lukas.coenig Jun 27 '16 at 20:52
9
$\begingroup$

The halting problem for DPDAs is not only decidable; it is computable in polynomial time.

Given a PDA $P$ and an input $x$, you can efficiently test whether $x$ is accepted by $P$. This can be done in time polynomial in the length of $x$ and the size of $P$. In particular, this is a terminating computation, so that means that the acceptance problem (given $P,x$, does $P$ accept $x$?) is decidable for PDA's.

Here is one way to see how. Let $X$ denote the language containing only $x$, i.e., $X=\{x\}$. $X$ is finite, so it is regular. Now the intersection of a context-free language with a regular language is also context-free, so $L(P)\cap X$ is context-free. You can test whether a context-free language is empty or not in polynomial time. So, test whether $L(P) \cap X$ is empty or not; this tells you whether $P$ accepts $x$ or not.

This holds even for non-deterministic PDAs.

Now, suppose we take a DPDA $P$, and modify it to transition to some new state $q_\text{final}$ if and only if it would halt (this can be done). Mark $q_\text{final}$ as an accepting state and all others as non-accepting, so it accepts by accepting state and accepts iff it reaches state $q_\text{final}$.

Then, test whether the modified PDA accepts the input $x$. By the above, this is decidable (and computable in polynomial time). This tells us whether the original PDA halts on input $x$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Sorry, my question wasn't clear - I was just asking about deterministic PDAs (I'll edit the question; but I believe your note of caution may still remain as part of the answer). Your answer is great! Thanks! Can you point me in the direction of a paper or so which describes how this regular language would be built, though? $\endgroup$ – lukas.coenig Jun 27 '16 at 17:20
  • $\begingroup$ Sorry @D.W. but I am not yet convinced deciding halting for DPDA is easy! DPDA also can pop of course. Assume a DPDA pushes a sequence of symbols that it later decides not to use: we find ourselves in a finite "loop" reaching the same top-configuration repeatedly. For instance $\{ a^n b^m c^m \mid m,n \ge 1\} \cup \{ a^n b^m d^n \mid m,n \ge 1\}$ is a DPDA language pushing $a$'s and $b$'s, but when $d$ is read all $b$'s will be popped: we see the same top stack symbol? Also the language of stacks is clever, but you can also get into a loop cycling through the same finite sequence of stacks? $\endgroup$ – Hendrik Jan Jun 27 '16 at 22:27
  • $\begingroup$ @HendrikJan, 1. We need to look at the pair of $(q,\alpha)$ where $q$ is the current state and $\alpha$ is the symbol at the top of the stack, and look for transitions between those pairs. That fixes the problems you identify. Considering just the top of stack $\alpha$ isn't enough, for the reasons you articulate. 2. You're right, the business about set of stacks was buggy; it had the problem of considering only the stack configuration and ignoring the state. I edited it just now to fix it. In particular, the set of configurations is also regular, and that's sufficient for this problem. $\endgroup$ – D.W.♦ Jun 27 '16 at 22:39
  • 1
    $\begingroup$ Again, I do not agree. The statement "$P$ halts on input $x$ if and only if the set of configurations reachable from $x$ is finite" is simply not true. The DPDA may end in an infinite cycle within a finite number of configurations (meaning stack plus state). Of course, once you know that number is finite, the possible loop can be detected, but that is not part of your claim. Avoiding looping computations is important: they form the heart of the proof that DPDA are closed under complement. That proof (at least to me) is involved. $\endgroup$ – Hendrik Jan Jun 28 '16 at 21:21
  • 1
    $\begingroup$ Consider a DPDA that while reading $\varepsilon$ keeps changing the top symbol $A$ into $B$ and back to $A$ in the next step. That is what I consider an infinite computation on a finite number of configurations. $\endgroup$ – Hendrik Jan Jun 28 '16 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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