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

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

<p><strong>Basic Idea:</strong> 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.</p>

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

<p><em>Start of Stage:</em> 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.  <em>End of Stage.</em></p>

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

<p><strong>Question:</strong> 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.</p>

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

CC BY-SA 3.0
2015-07-23T22:09:30.543Z
This seems similar to Muller/Schupp 1985?
András Salamon
CC BY-SA 3.0
2015-07-24T03:35:59.480Z
@AndrásSalamon Cool!  Thank you for the reference.  :)
Michael Wehar
CC BY-SA 3.0
2015-07-24T21:59:43.357Z
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.
user4242
CC BY-SA 3.0
2015-07-25T04:15:47.837Z
@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.
Michael Wehar
CC BY-SA 3.0
2015-08-13T15:34:22.460Z
This might provide some relevant information: http://arxiv.org/pdf/1405.5593.pdf
Michael Wehar
CC BY-SA 3.0
2015-09-21T03:46:22.950Z
Update: I've talked with several people who work in automata theory and complexity.  It seems that this approach is fairly well known, but might not be in the classic textbooks.  If you find a textbook that includes this algorithm, please let me know.  :)
Michael Wehar
CC BY-SA 3.0
2015-07-23T03:46:25.433Z
2015-07-23T04:32:05.037Z
2015-07-23T04:32:05.037Z
Michael Wehar
<p>The emptiness problem for Context free Grammars(CFG) is well studied. The same holds for the equivalence problem between Pushdown Automata (PDA) and CFGs. </p>

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

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

<automata-theory><grammars>
Emptiness of PDA without constructing the corresponding CFG
user4242
# Emptiness of PDA without constructing the corresponding CFG

(Asked by: username_0 on 2015-07-22)

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.

**Tags:** automata-theory, grammars


---

## 1 answers

### Answer by username_1 on 2015-07-23. Score: 4 | Accepted answer

**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! :)

> **Comments:**
> **username_2**: This seems similar to Muller/Schupp 1985?  
> **username_1**: @AndrásSalamon Cool!  Thank you for the reference.  :)  
> **username_0**: 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.  
> **username_1**: @username_0 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.  
> **username_1**: This might provide some relevant information: http://arxiv.org/pdf/1405.5593.pdf  
> **username_1**: Update: I've talked with several people who work in automata theory and complexity.  It seems that this approach is fairly well known, but might not be in the classic textbooks.  If you find a textbook that includes this algorithm, please let me know.  :)  

---

