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 ?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
answered Dec 4, 2016 at 14:57
-
$\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$ Dec 4, 2016 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$ Dec 6, 2016 at 18:42