0
$\begingroup$

I have a very basic question. Can we have a PDA which can accept a string by both final states and empty stack? Can the same PDA accept by the two modes simultaneously ? If there are final states for acceptance and in addition to that at some point in time the input string is read completely and simultaneously the stack is empty but the state is non-final. Will it be accepted in that case ?

$\endgroup$

migrated from stackoverflow.com Dec 4 '16 at 13:33

This question came from our site for professional and enthusiast programmers.

1
$\begingroup$

Yes, that is possible. If you start with one that accepts by final state, you can change that one into an automayon that accepts by final state and empty stack as follows.

First create a new final state $f$. From every old final state have an epsilon transition to the new state $f$. Add transitions to $f$ that empty the stack.

It seems best to keep the old final states. A computation of the old automaton might end in one of the old final states with an empty stack, in which case it should be accepted, but we have no contents of the stack, so we cannot move to $f$.

$\endgroup$
  • $\begingroup$ I meant to ask can we have the same PDA accept by the two modes simultaneously ? Like there are final states and at some point of time the input string is read completely and simultaneously the stack is empty but the state is non-final. $\endgroup$ – Gaurav Mitra Dec 4 '16 at 17:50
  • $\begingroup$ Do you mean a construction where both modes give the same language? Where computations of a PDA move to a final state and empty the stack simultaneously? (And not one without the other?) $\endgroup$ – Hendrik Jan Dec 6 '16 at 18:42

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.