Acceptance of languages by DPDA with empty stack Vs NPDA with empty stack

Question

There are two possible acceptance criteria: acceptance by empty stack and acceptance by final state. The two are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by empty stack are those languages that are accepted by final state and are prefix-free: no word in the language is the prefix of another word in the language.

This is the quote from Wikipedia....plz explain why acceptance by empty stack and acceptance by final state are not equivalent in case of DPDA but it is equivalent in case of NPDA 

Comments

Prefix property : In simple words if a language has a string x then that language should not have any string xy where y≠∈. This means there can be no string in the language present which has it's prefix present as well in the language.

If xy is a string present in L whose prefix x is also a part of L then such language is said to have no prefix property.

Eg: L={∈,a,aa,aaa,aaaa,....} i.e. a*

Here aa is a string those proper prefixes are ∈,a. ∈,a belong to L. So this language has no prefix property.

Now as your statement says that DPDA with empty stack cannot accept languages which does not have prefix property.

To prove this I assume that this statement is false and try to use proof by contradiction.

So let L be a language containing x and xy ( y≠∈ ) and L is accepted by DPDA with empty stack.

Let the start state be q₀ and the DPDA is given string x.

Then after some transitions when we finish taking all the characters in string x we will reach a state (say p) where the stack becomes empty and we know that x is accepted by DPDA.

(q₀,x,Z₀) ------->^*  (p,∈,∈)

Next we take xy into the DPDA. Since it contains x as a part of it then it's clear that it will follow the same initial transitions as before and ultimately will reach state p where it is left with "y" but the stack has become empty!

(q₀,xy,Z₀) ------->^*  (p,y,∈)

This means that without checking the whole string we have come to an empty stack situation from where we can't proceed further! DPDA cannot make any further transitions on empty stack but part of i/p is still left.

When is a string accepted? When stack is empty and we reach the end of the string.

So, xy is not accepted by DPDA with empty stack.

Next question is how NPDA deals with such languages?

This is because NDPA has more than 1 choice for a particular configuration. Even if it gets stuck in this situation with empty stack and input left ≠∈ it can have other routes to explore.

I take the example of aa* and try to make NPDA that accepts by empty stack.

I don't know whether this is a minimized state NPDA or not.

1.(q₀,a,Z₀) -> (q₁, ∈ )  // pop Z₀ on a and move to state q₁ -->this accepts "a"

2.(q₀,a,Z₀) -> (q₂, Z₀)  // Do nothing on a and move to state q₂

3.(q₂,a,Z₀) -> (q₂, Z₀)  // Do nothing on a and remain in state q₂

4.(q₂,a,Z₀) -> (q₁,∈)  // pop Z₀ on a and move to state q₁

In case of DPDA we don't have any other choice after rule 1. Here in NPDA we can move to state q₂ and remain there until we want to pop Z₀.

Take string a

(q₀,a,Z₀) --> (q₁,∈)  //Stack is empty now

Take string aa

(q₀,a,Z₀) --> (q₂,Z₀) 

(q₂,a,Z₀) --> (q₁,∈)

Does this clear your doubt?

---

@MiNiPanda

I skipped this one at that time & thought that I would by heart this... & today I again came across this type of question & I read urs explanation 2-3 times and got the concept...Thanks Sir!

---

Welcome @himgta :)  

---

@minipanda nicely explained

---

Thanks Brother, it helped alot.

---

@MiNiPanda, what a nice explanation, grateful

 

---

Thanks @MiNiPanda