629 views
1 votes
1 votes
The language accepted by a DPDA with a final state is more compared to the DPDA with empty stack.

DPDA with empty stack accepts LR(0) grammar.

Can someone explain in depth/or give good reference links?

1 Answer

0 votes
0 votes
The main reason why acceptance by final state is more powerful than acceptance by empty stack is because the latter requires the ‘PREFIX property’ to be satisfied.

What is prefix property?

It means that no string of a given language is a prefix of other string of the same language i.e. if ‘aax’ belongs to the language then ‘aaxx’ or ‘aaxa’ cannot belong to the same language.

Why is it a problem?

Because since ‘aax’ is accepted by empty stack, therefore while processing ‘aaxx’, the stack will get empty with one ‘x’ left to process. And since we have no rules defined for it, the language will not be accepted.

Why LR(0) is being accepted?

Because LR(0) also requires prefix properties to be satisfied, unlike other LR parser. And therefore DPDA by empty stack can easily process all LR(0) language.

Related questions

0 votes
0 votes
0 answers
1
Satbir asked Dec 10, 2018
447 views
Consider the following PDA:The language accepted by the given PDA is: L = {(b^n a b^n a )^m | m, n >= 0} L = {b^n a b^n a | n >= 0} {bn | n >= 0} L = {b^n a b^n a | n >= ...
1 votes
1 votes
1 answer
2
aditi19 asked Sep 3, 2018
1,942 views
what is the DPDA for L=$a^{2n+1}b^n$ | n>1
0 votes
0 votes
0 answers
3
aditi19 asked Sep 3, 2018
310 views
L=$a^mb^n$ | m!=nis the following DPDA correct for the mentioned language?
0 votes
0 votes
0 answers
4
aditi19 asked Sep 2, 2018
995 views
what is the PDA for {L=$a^mb^n$ |m>n}