2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ You can convert the PDA to a CFG and then use the CYK algorithm on the resulting CFG. $\endgroup$
    – rici
    Commented Jan 4, 2022 at 17:20
  • $\begingroup$ @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. $\endgroup$
    – Hendrik Jan
    Commented Jan 4, 2022 at 20:21
  • $\begingroup$ @hendrik: yes, that's part of preparing the cfg for cyk. But it's always possible. $\endgroup$
    – rici
    Commented Jan 4, 2022 at 20:27
  • $\begingroup$ 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. $\endgroup$
    – Hendrik Jan
    Commented Jan 4, 2022 at 20:52

2 Answers 2

Reset to default
3
$\begingroup$

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.2 (Pushdown Systems) 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. (access via Springer, Google Books, or Internet Archive)

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ The mentioned article and its citations seem to discuss only "pushdown systems" (PDSs), which don't have an input that they accept/reject. How does one go from these results on PDSs to PDAs? $\endgroup$
    – Electro
    Commented Oct 4, 2023 at 13:12
  • $\begingroup$ @Electro, that is explained in the paragraph beginning "Now, given an input word ...". $Q$ can be viewed as a PDS. $\text{post}^*(Q)$ contains an accepting configuration iff $x \in L(P)$. $\endgroup$
    – D.W. ♦
    Commented Oct 4, 2023 at 17:32
  • $\begingroup$ So, if I understand this correctly, we are essentially building the input $x$ into the PDA $P$ to convert it into an almost-PDS $Q$. Since any accepting path in $Q$ corresponds to reading in exactly the input, it follows that $P$ accepts $x$ iff $Q$ accepts anything. That is, all we need to do is check whether $L(Q)$ is empty. To do this, we turn $Q$ into a PDS $R$ by deleting the input component of each transition, and then check whether $R$ can reach any of $Q$'s accept states after being started in $Q$'s start state with an empty stack. $\endgroup$
    – Electro
    Commented Oct 11, 2023 at 4:51
  • $\begingroup$ @Electro, yes, that's correct. $\endgroup$
    – D.W. ♦
    Commented Oct 11, 2023 at 4:55
  • $\begingroup$ I'm trying to follow the algorithm for $\mathrm{post^*}(C)$ given in the book, on page 17 they show an example for the ICFG program on page 14. The algorithm is not described clearly and I cannot understand why there is a transition from state $p$ to the accepting state using stack symbol $n_4$. I can only make a epsilon transition from $p$ to $p_{ef}$, which then has a transition to the accepting state using symbol $n_4$. Also the $\mathrm{pre^*}(C)$ seems too simple, I cannot derive that $e_{main}$ is backward reachable from $x_{main}$. What could I be misunderstanding? $\endgroup$
    – Jerry Ding
    Commented Mar 9 at 7:52
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$
    – Hendrik Jan
    Commented Jan 4, 2022 at 15:59
  • $\begingroup$ You are right! I unconsciously worked without $\varepsilon$-moves. $\endgroup$
    – Nathaniel
    Commented Jan 4, 2022 at 19:11
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Jan 5, 2022 at 1:08

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.