pushdown automata

Question

What is the difference between DPDA which accept Language by the empty stack and the one which accepts by final state

Comments

In Case of DPDA, Languages accepted by empty stack is a proper subset of languages accepted by final state mechanism.

Answer 1

Push down automaton, In a final state PDA accepts a string, when and after reading the entire string, the PDA is in a final state.

 

The stack values in PDA can be irrelevant as long as the values ends up in final state.

 

Empty stack accepts a string when after reading the entire string, the PDA has emptied its stack.

Answer 2

well , the difference is quite huge

 

DPDA that accepts language by empty stack have a special property that, these type of languaeg have prefix property( a language whose strings  have no prefix in the set of strings contained in the language is said to have prefix property).

DPDA that accepts language by final state can accept all the language that can be accepted by empty stack DPDA but converse is  not true. reason being when you try to convert Final stack dpda for a language having prefix property to DPDA having empty stack method , you will have to add an epsilon- transition thus making it NPDA