1
$\begingroup$

Can the same PDA accept both by final state and empty stack in the sense that there are some set of strings that are getting accepted by empty stack, while other set of string by final state and language accepted by the PDA is union of these two?

For example, Consider the PDA shown below:- PDA

I was trying to figure out the language accepted by this PDA and I got confused on the point that a string w=b is given as input, that will be popped out and the stack will be empty so would b be an element of language accepted by PDA or if we consider it only as acceptance by final state (considering that acceptance by final stack requires the bottom of stack symbol to be left in the stack ) the language accepted by this PDA will be :

{w| any prefix of w has number of a's more than number of b's}

However a string like "ab" can also be accepted if we allow both acceptance by empty stack and final state (The confusion here is strictly more a's or it can be equal too).

$\endgroup$
  • 1
    $\begingroup$ You can define whatever model of computation you want. The two standard models of computation for PDA, however, are “final state” PDAs and “empty stack” PDAs. When describing a PDA, we have to state which of these two we’re using. $\endgroup$ – Yuval Filmus Dec 22 '18 at 11:45
  • $\begingroup$ @YuvalFilmus So since this PDA accepts by final state, so would the language of this PDA include "b"? $\endgroup$ – Amisha Bansal Dec 22 '18 at 14:44
  • 1
    $\begingroup$ The PDA accepts all strings having a computation ending at a final state. $\endgroup$ – Yuval Filmus Dec 22 '18 at 14:52
1
$\begingroup$

Since it was not explicitly mentioned, I'll assume that the PDA in the question is a PDA $P_s$ that has been defined for acceptance by empty stack. Let the language accepted by $P_s$ be $L_s = N(P_s)$.

There definitely exists another PDA $P_f$ which produces a language $L_f = L_s$ by defining acceptance on final state. This is why we say that:

A language L has a PDA that accepts it by final state if and only if L has a PDA that accepts it by empty stack.

However, it is wrong to expect that the two PDA $P_s$ and $P_f$ are the same.

$\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.