Register

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

• edited by
5,415 views
10 10 votes

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 

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← Previous · Disk SchedulingNext → · Inclusion-Exclusion
← Previous in category · toc bookNext in category → · SELF DOUBT
Position:
Show:

Related questions

1 1 vote
0 0 answers
2.5k
2.5k views
Matrix asked Jul 28, 2018
2,495 views
DPDA acceptance by empty stack
Is this approach of acceptance by empty stack correct ?I am confused because i have read that acceptance by empty stack may not be able to accept all regular languages.
7 7 votes
1 1 answer
3.6k
3.6k views
Himanshu1 asked Jan 3, 2016
3,553 views
DPDA (Empty Stack vs Final State)
" DPDA acceptance with empty stack" & " DPDA acceptance with Final State" are not equivalent. Comment on their dissimilarities & why they are not equivalent ?
1 1 vote
1 1 answer
3.3k
3.3k views
daksirp asked Jul 25, 2018
3,273 views
Equivalence of acceptance by empty stack and acceptance by final state. : PDA, Prefix Property
Set of languages accepted by DPDA by empty stack contain only those DCFL’s with prefix property.and DPDA with empty stack doesnt accept any regular language too becaust i...
1 1 vote
1 1 answer
2.8k
2.8k views
rahul sharma 5 asked Jul 31, 2017
2,796 views
TOC DPDA vs NPDA
How many stacks are available with DPDA and NPDA? I assume it is 1 with DPDA and n with NPDA where n is some constant.Assume i have a language ,over alphabet a,b,c,dL=( W...