1
$\begingroup$

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. Extended non-deterministic pushdown automata

$\endgroup$
2
  • $\begingroup$ A related post, Is it decidable for a NPDA to halt? $\endgroup$
    – John L.
    May 20 at 18:01
  • $\begingroup$ 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$? $\endgroup$
    – John L.
    May 20 at 18:03

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.