5
$\begingroup$

The emptiness problem for Context free Grammars(CFG) is well studied. The same holds for the equivalence problem between Pushdown Automata (PDA) and CFGs.

Therefore, given a PDA, the straightforward way to decide whether the language it accepts is empty is to convert the PDA into a CFG and then use the known algorithm to decide emptiness of the corresponding CFG.

I am wondering whether there exists some algorithm to directly check emptiness of the language of the PDA without going through the conversion to a context free grammar.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

Quick Answer: Yes, there is a really lovely algorithm that solves non-emptiness for pushdown automata that does not involve constructing the equivalent CFG.

Possible Drawback: Correct me if I am wrong, but it doesn't appear to be more efficient than the approach where you convert to a CFG.

Basic Idea: It can be viewed as a sort of dynamic programming algorithm where you solve reachability without ever constructing the possibly exponential length paths that you need to consider.

You start with a state diagram for a Pushdown Automata. Let's call a transition that doesn't manipulate the stack a resting transition. You proceed with a series of stages.

Start of Stage: You combine all compatible push and resting transitions. Next, you combine all compatible pop and resting transitions. Then, you combine all compatible pairs of resting transitions with each other. Finally, you combine all compatible push and pop transitions. Now, you throw in all of the new transitions into the state diagram. End of Stage.

You go through stage after stage repeating this process. There are only so many possible transitions. Eventually, you either get a transition that leads from the start state to a final state or you must run out of possible transitions to add. At this point, you know whether the automata's language is empty or not.

Question: Can you provide me with any books or papers that give a good exposition of this algorithm? Whenever I searched for it several years ago, it seemed that this algorithm is unpopular or not well known. I personally really like it.

Thanks for asking the question! I really appreciate it and I hope this helps a little bit. Have a nice day! :)

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ This seems similar to Muller/Schupp 1985? $\endgroup$
    – András Salamon
    Commented Jul 23, 2015 at 22:09
  • $\begingroup$ @AndrásSalamon Cool! Thank you for the reference. :) $\endgroup$
    – Michael Wehar
    Commented Jul 24, 2015 at 3:35
  • 1
    $\begingroup$ Thanks! Regarding the drawback of not being more efficient, we do some operations between automata and want to check emptiness of the resulting PDA, thus going back to a CFG would require an extra engineering effort and thats why this algorithm comes very handy in our case. $\endgroup$
    – user4242
    Commented Jul 24, 2015 at 21:59
  • $\begingroup$ @user4242 Cool! Could you possibly elaborate further with me via email? My thesis work is on non-emptiness and intersection non-emptiness problems. I'm especially interested in non-emptiness problems for automata with stacks. Hearing more about your project could really benefit me in understanding the ongoing practical applications and I could hopefully benefit you by sharing more relevant results. $\endgroup$
    – Michael Wehar
    Commented Jul 25, 2015 at 4:15
  • $\begingroup$ This might provide some relevant information: arxiv.org/pdf/1405.5593.pdf $\endgroup$
    – Michael Wehar
    Commented Aug 13, 2015 at 15:34

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.