# Algorithm to detect if word belongs to pushdown automaton

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?

• If you convert your automaton to a grammar, you can use the CYK algorithm. – adrianN Dec 16 '16 at 16:17
• 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. – 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}$.