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 states 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 on the 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, imput 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 &quot;this branch goes nowhere, terminate it&quot;?
Here is an example automata - accepts palindromes.
Take a look at this post.
A general way to remove epsilon transitions is to transform the PDA into a CFG, then take this grammar and convert it back to a PDA. This will result an equivalent PDA that does not need epsilon transitions. Take a look here for the algorithms converting the PDA to CFG and back.