# Extended NPDA implementation

In Formal Grammars course we have a task to implement an extended NPDA (a pushdown automata where taking any amount of symbols from the stack is allowed (including ε) and it can be in several configurations at the same time) in any programming language. It can be one that accepts with a state or an empty stack.

I have looked around and all implementation algorithms I have found do not allow for transitions like (ε/ε)/A (read nothing, take out of stack nothing, just add A to stack). The problem of course is that there is (as far as I know) no sure way to terminate this kind of branch and, if indeed, input string does not belong to this language, it would just infinitely try to loop and loop these kinds of transitions.

So, my question is - how to implement an extended NPDA? How to know when to stop generating a branch and say "this branch goes nowhere, terminate it"?

Here is an example automata - accepts palindromes.

• A related post, Is it decidable for a NPDA to halt? May 20 at 18:01
• It looks like you are asking how we can know when to stop extending a branch and say this branch can be ignored. Given an extended npda, there should be a constant $c$ and $k$ such that for any $w$ that is accepted, there is a branch that accepts it with no more than $c|w|^k$ steps. In this sense, every extended npda is effective. Can $k\le3$ or even $k=1$? May 20 at 18:03