I am creating a simple program to detect if the given pushdown automaton accepts the given word, and I have a problem in finding an algorithm that does that.

My thought at first would be to go through all possible transitions, and check if we didn't match this word in accepting state, but got in problem with (epsilon, epsilon)/V where we can put V into stack without reading anything and getting from stack.

Is there any good algorithm which could work, or is this task impossible?

Example automaton

  • 3
    $\begingroup$ If you convert your automaton to a grammar, you can use the CYK algorithm. $\endgroup$ – adrianN Dec 16 '16 at 16:17
  • $\begingroup$ Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. If you post image, please take some time to make it high contrast, representing the crucial part and if possible write math in LaTeX and use some tools to create diagrams. For example here you can create the diagram at the bottom. Thank you. $\endgroup$ – Evil Dec 16 '16 at 21:24

As adrianN notes in their comment, your task is certainly algorithmically possible. There are algorithms that take a PDA $A$ and outputs a context-free grammar $G$ such that $L(A) = L(G)$, and others (such as CYK) that take a context-free grammar $G$ and a word $x$ and determine whether $x \in L(G)$.

There might be shortcuts, but at least this shows that your problem is decidable. In fact, since both algorithms run in polynomial time, the problem belongs to $\mathsf{P}$.

Judging from the literature, it seems that this chain of reductions is the standard way of solving the membership problem for pushdown automata. See for example these notes from Hendrik Jan Hoogeboom and Joost Engelfriet.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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