3,372 views

1 Answer

Best answer
38 votes
38 votes

Prefix Property: If a string is a member of the language then no proper prefix of that string should be a member of the language.
For example, if L= a* then string 'aaa' is a member of the language L, and 'aa' is prefix of 'aaa' and 'aa' is also a member of the language hence the language L = a* doesn't satisfy prefix property.

Now, there is another language L1 = a*b, members of this language are b, ab, aab, aaab and so on.. now you can see if aaab is the member of the language then no proper prefix of 'aaab' is in the language.
Prefix(aaab) = {eps, a, aa, aaa, aaab} 
Hence, this language L1 satisfies prefix property.

Why a DPDA with 'empty stack acceptance' can't be constructed for a DCFL which doesn't satify prefix property?
It's because it can accept those strings also which are not the members of the language. 
for example
L = a*  this is a regular language, hence, it is dcfl too. So, we should be able to construct a DPDA with empty stack acceptance for this language.
As 'aa' is the member of the language, it should be accepted by the corresponding DPDA. When you feed 'aa' to the DPDA, at the end of 'aa' stack will become empty and DPDA declares that given string is accepted.

Now, consider a contradiction, suppose given string is 'aab' and this doesn't belong to the language hence it should be rejected by the DPDA, but when you start feeding 'aab' to the DPDA, as soon as you provide 'aa' to the DPDA, stack will be empty and DPDA declares that the given string is accepted and is the member of the language, which is wrong! 

Few points to be noted here,

1. DPDA with empty stack acceptance has lesser power than DPDA with final state acceptance. As we have shown there is no DPDA with empty stack constructed for L=a* while we can make a DPDA for this language with final state.

2. NPDA with empty stack has the same power as NPDA with final state.

3. We can construct a DPDA with empty stack for all those DCFLs which satisfy prefix property.

4. If you want to construct a DPDA with empty stack for all the DCFLs then suffix a '$' with the language, it means if our language is L=a*, then modify this language to L$ make sure that '$' is not a part of input alphabets. it assures that no prefix of a member will also be a member of the language, therefore, we can construct a DPDA with empty stack for all the DCFLs.

 

selected by

Related questions

0 votes
0 votes
1 answer
1
sumitr asked Apr 23, 2018
468 views
8 votes
8 votes
3 answers
2
0 votes
0 votes
2 answers
3
Shamim Ahmed asked Oct 25, 2018
1,148 views
Among Deterministic pushdown automata and Non deterministic pushdown automata, which is more powerful and why ?
0 votes
0 votes
0 answers
4