Register

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

• edited by
4,166 views
9 votes
9 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 

• edited by
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
0 answers
1
Matrix asked Jul 28, 2018
1,549 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.
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.
User Avatar
7 votes
7 votes
1 answer
2
Himanshu1 asked Jan 3, 2016
3,085 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 ?
" DPDA acceptance with empty stack" & " DPDA acceptance with Final State" are not equivalent. Comment on their dissimilarities & why they are not equivalent ?
User Avatar
Link Copied!