GATE CSE 1999 | Question: 1.6

Question

Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?

• A. $L_1 = L_2$
• B. $L_1 \supset L_2$
• C. $L_1 \subset L_2$
• D. None

Comments

if it is ask about dpda the B will be answer

---

for more explanation - 

https://gateoverflow.in/249558/acceptance-languages-dpda-with-empty-stack-npda-empty-stack

https://csedoubts.gateoverflow.in/5180/self-doubt-dcfl

---

@Deepak Poonia Sir, But it might be possible that set of all languages accepted by a PDA by final state and set of all languages accepted by empty stack may not be equivalent.
 

---

@harshitraj12,

(Set of all languages accepted by a PDA by final state) $=$ (Set of all languages accepted by empty stack)

Answer 1

Answer to the question is (A) $L_1 = L_2$.
Reason is for any PDA which accepts by final state there is an equivalent PDA (equivalent means that accepts the same language) which accepts by empty stack and vice-verse. 

Now, this is not the case for DPDAs.

The set of languages accepted by a DPDA by empty stack is a strict subset of the set of languages accepted by a DPDA by final state. 

It can also be said that set of languages accepted by a DPDA by empty stack is the set of languages accepted by a DPDA by final state and which has the prefix property. 

A language has prefix property means if $w \in L$, then no proper prefix of $w \in L$. 

From the above definition of prefix property it must be clear why DPDA by empty stack has this property. If any prefix of a word $w$ ($w$ in $L$) is in $L$ means the stack should have been empty even before completely processing $w$. But, being a deterministic PDA, once the stack becomes empty, the DPDA accepts and halts. So, in no way can a DPDA accepts $w$ and its prefix. 

PS: A DPDA with acceptance by empty stack cannot even accept all regular languages- example $a^*$. 

Good read: http://www.cs.ucr.edu/~jiang/cs150/slides4week7_PDA+EquivToCFG.pdf

Comments

Means to accept by empty stack in dpda ,it should have prefix property.Hence languages accept by dpda empty stack is subset of languages accepted by final state ? @Deepak Poonia sir

---

The set of languages accepted by a DPDA by empty stack is a strict subset of the set of languages accepted by a DPDA by final state. 

I believe the explaination for this could be given more, the core idea revolves around prefix-property, 
 

Prefix property, simply means if a word say u.v belongs to Language, then it's prefix u should not belong to the Language, one eg would be L = (a)* 
In this language, if aaa belongs to L, it's prefix epsilon, a, aa also belongs to L, thus this language does not exhibit prefix property, 

A DPDA that ends with empty stack cannot accept languages that do not have prefix property, that is why there does not exist a DPDA which accepts L = a*, but it might really be conflicting to the idea that DPDA are generally more powerful that Finite automa and we expect DPDA to accept L = a* since it is already accepted by a Finite automata, 

The reason is beautifully explained in this post link

However the reason is very simple, before explaining the reason, just know L = a* is not accepted by DPDA with empty stack while it is accepted by DPDA by final state, this is the whole point of this post, this is why set of lang accepted by dpda by empty stack is a strict subset of set of lang accepted by dpda by final state, 

Final Reason: 
the problem that DPDA by empty stack is very simple, the idea is to accept the lang by this Machine, you have to literally empty the stack, which also includes the z0, basically the stack must be literally empty, 
now say if we construct a DPDA with empty stack that accepts the Language

L = { ab, aba }

In this language inorder to accept ab, irrespective of the configuration you have to empty the stack, and once emptied you can make the machine accept ab, now because it is a Deterministic machine and you will try to accept another string aba, while processing the first two symbols you are guarenteed to stand in the same place where you were at the first string, that is empty state, now you have a make a transistion to somehow read the 3rd character a, but the problem with this transition is that, you need to specify the top of the stack, mentioning epsilon doesn't make sense and it is not how it works with DPDA that accepts by empty stack, one the stack is empty the machine will automatically halt, you cannot define another transition.

This restriction is not in the case of DPDA that is accepted by finite state, you don't even care about the stack just define two finite states, and push everything, it is as simple as that, hope it helps.

---

thanks @nareshit 

Answer 2

The point of confusion hear is the word PDA.

When we say PDA with generally refers to NDPA. Now ndpa has two ways of acceptance either by empty stack or by final state. In both the cases language accepted by any one of them will be accepted by the other. But if it is specifically mention that it's a DPDA then the answer will be changed as in DPDA, there are some languages which are accepted by final state but not by empty stack.​​​​​