0
$\begingroup$

The classic solution for the membership problem of a language generated by a PDA is to convert said PDA to a CFG and then to use CYK or a similar algorithm. I was wondering if there are any known algorithms to solve this problem without a conversion to a CFG.

My attempt at a naive solution was to "emulate" a PDA, but if there's a transition of form $(q, \varepsilon, A, q, AA)$, then the stack grows infinitely and emulation never halts.

Improve this question
$\endgroup$
4
  • $\begingroup$ "Without conversion to a CFG" is not an objectively measurable criterion. I can always write down an algorithm that is effectively converting in place to a CFG and testing membership, or isomorphic to that, but without making the connection explicit. Is there some reason you've rejected that approach? Perhaps you have a running time requirement, or something else? I do know of algorithms that don't involve an explicit conversion, but I don't immediately see what advantage they have over the standard approach. $\endgroup$
    – D.W. ♦
    Jun 9, 2020 at 3:58
  • $\begingroup$ For instance, you might be interested in Tomita's algorithm, or generalizations of it. $\endgroup$
    – D.W. ♦
    Jun 9, 2020 at 4:00
  • $\begingroup$ My question is purely theoretical; I'm not looking for any specific advantages, I just want a different approach to the problem. $\endgroup$
    – lsparki
    Jun 9, 2020 at 10:14
  • $\begingroup$ Tomita's algorithm works only for non-cyclic grammars though, which is the same problem as my naive solution. Have there been any improvements of that algorithm to account for cycles? I haven't found any. $\endgroup$
    – lsparki
    Jun 9, 2020 at 10:18

1 Answer 1

Reset to default
1
$\begingroup$

Yes, it is possible. Given a pushdown automaton $P$ and a word $x$, you can easily construct a new pushdown automaton $P'$ such that $L(P') = L(P) \cap \{x\}$. This works by using a product construction to expand the finite-state control of $P$ by a factor of $n$, where $n$ is the length of $x$.

Now, you can test whether $P$ accepts any non-empty word. One way to do this is by computing the set of all reachable configurations of $P$. This set is an infinite set, but it turns out to be a regular set, and you can construct a finite automaton that represents the set of reachable configurations. One way to do that is using an algorithm for computing post*; see Section 2.2.2 of Analysis Techniques for Information Security, by Anupam Datta, Somesh Jha, Ninghui Li, David Melski, and Thomas Reps. (You can view this as an improvement to Tomita's algorithm that works for arbitrary PDAs, not merely the ones that arise from a LR(k) parser. Cycles are not a problem.)

This may be morally isomorphic to converting $P$ to a context-free grammar, intersecting that grammar with the regular language $\{x\}$ using the product construction, and then using standard algorithms to test whether that generates a non-empty language. That in turn may be morally isomorphic to converting $P$ to a context-free grammar and then using CYK parsing.

The running time of all of these methods is $O(n^3)$, so while the algorithm looks different on paper, it does not lead to any improvement in running time. The PDA-based approach does have the advantage that it is easily adapted to on-the-fly processing of the word $x$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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