# Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?

Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if a PDA accepts a string or not. Some would recommend the CYK algorithm, but that's for a CFG in CNF, not for a PDA. If there is no algorithm for us to use it, why would we need to invent PDAs? I also find that materials on this subject is suprisingly scarce on the Internet.

Some would suggest me to run the PDA by feeding input symbol to it and see if it accepts by empty stack or final state. But because a PDA may contain multiple transitions relevant to an input symbol, it's us who have to choose among these transitions and that's not an algorithm (which must be completely automatic). That's utilizing our own observation and thinking.

• You can convert the PDA to a CFG and then use the CYK algorithm on the resulting CFG.
– rici
Jan 4 at 17:20
• @rici After the PDA-to-CFG conversion you then have to do another conversion into Chomsky normal form, which includes the removal of $\varepsilon$-productions. Jan 4 at 20:21
• @hendrik: yes, that's part of preparing the cfg for cyk. But it's always possible.
– rici
Jan 4 at 20:27
• Just had a look at the wikipedia page for the CYK algorithm, especially the remarks on non-ChomskyNF grammars. The Lange and Leiss 2009 reference is very interesting. It shows how the complexity of the ChNF reduction depends on the order of the applied steps. (This was known to me, but the analysis here is very complete.) Moreover it shows how to remove nullable symbols in an efficient way. Jan 4 at 20:52

Yes, there are. There is an algorithm that, given any PDA $$P$$ and any input word $$x$$, directly checks whether $$x$$ is accepted by $$P$$, without first converting $$P$$ to a CFG. The algorithm takes running time $$O(n^3)$$ (treating the size of $$P$$ as a constant that is absorbed into the big-O notation).

The idea is that, given a PDA $$P$$, we can compute a representation of the set of all possible configurations of the PDA on all possible inputs. This set is traditionally denoted $$\text{post}^*(P)$$. It is typically an infinite set (thanks to the $$\epsilon$$-transitions in $$P$$), but we are rescued by the following beautiful property: $$\text{post}^*(P)$$ is always a regular language. Therefore, it can be represented by a NFA. Moreover, there is an efficient algorithm to compute a NFA that represents $$\text{post}^*(P)$$, given $$P$$.

Now, given an input word $$x$$, we construct a DFA $$D$$ that accepts only $$x$$ and no other word. Then, we use the product construction to construct a PDA $$Q$$ that accepts an input word iff both $$P$$ and $$D$$ accept that word. Next, we compute $$\text{post}^*(Q)$$ using the aforementioned algorithm. Finally, we check whether $$\text{post}^*(Q)$$ contains any accepting configuration (i.e., a configuration where both $$P$$ and $$D$$ accept); this is straightforward since we have a representation of $$\text{post}^*(Q)$$ as a NFA.

The theory has been worked out in the model checking community. You can find an overview of the foundations and references where you can learn more, in Section 2.2.3 of the following survey paper (there are probably many other expositions as well):

Analysis Techniques for Information Security. Anupam Datta, Somesh Jha, Ninghui Li, David Melski, and Thomas Reps. Synthesis Lectures on Information Security, Privacy, and Trust, 2010 April 27, vol 5, no 1, pages 1--164.

The resulting algorithm has various nice properties. For instance, if you work through what the construction is doing, you can convert it to an online algorithm that reads one symbol of the input at a time and then updates the set of reachable configurations, in case that is helpful to you. It is possible to view this as a generalization of Tomita's algorithm for GLR parsing, except that Tomita's algorithm only works if the PDA is a LR parser, while the above works for any PDA.

Given a pushdown automaton $$A = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$$, define a configuration as a couple $$(q, \gamma)$$, with $$q\in Q$$ and $$\gamma\in \Gamma^*$$. A configuration represents the state $$q$$ of the PDA, and the stack word $$\gamma$$.

If there are no $$\varepsilon$$-transition (and you can always find such a PDA), given a word $$u$$, you can decide if $$u$$ is accepted by $$A$$ by computing the set of possible configurations reachable from $$(q_0, Z_0)$$ by reading $$u$$, and verifying if this set contains an accepting configuration (either by final state or empty stack, depending on the PDA).

This can be done in polynomial time in the size of $$u$$.

This is a similar method to the one to decide if a word is accepted by a non-deterministic finite automaton.

• This is nontrivial if you need to deal with $\varepsilon$ rules that push, I think. The set of reachable configurations might be infinite. Unless there any bound on the stack height? Jan 4 at 15:59
• You are right! I unconsciously worked without $\varepsilon$-moves. Jan 4 at 19:11
• Yeah, this doesn't work, because the set of reachable configurations is typically infinite (thanks to $\epsilon$-transitions), but the basic idea can be made to work with more work -- see my answer for how.
– D.W.
Jan 5 at 1:08