+29 votes
3.4k views

Let $L_1$ be the set of all languages accepted by a PDA by final state and $L_2$ the set of all languages accepted by empty stack. Which of the following is true?

1. $L_1 = L_2$
2. $L_1 \supset L_2$
3. $L_1 \subset L_2$
4. None
asked
retagged | 3.4k views
+3
if it is ask about dpda the B will be answer

## 1 Answer

+60 votes
Best answer

Answer to the question is (A) $L_1 = L_2$.
Reason is for any PDA which accepts by final state there is an equivalent PDA (equivalent means that accepts the same language) which accepts by empty stack and vice-verse.

Now, this is not the case for DPDAs.

The set of languages accepted by a DPDA by empty stack is a strict subset of the set of languages accepted by a DPDA by final state.

It can also be said that set of languages accepted by a DPDA by empty stack is the set of languages accepted by a DPDA by final state and which has the prefix property.

A language has prefix property means if $w \in L$, then no proper prefix of $w \in L$.

From the above definition of prefix property it must be clear why DPDA by empty stack has this property. If any prefix of a word $w$ ($w$ in $L$) is in $L$ means the stack should have been empty even before completely processing $w$. But, being a deterministic PDA, once the stack becomes empty, the DPDA accepts and halts. So, in no way can a DPDA accepts $w$ and its prefix.

PS: A DPDA with acceptance by empty stack cannot even accept all regular languages- example $a^*$.

Good read: http://www.cs.ucr.edu/~jiang/cs150/slides4week7_PDA+EquivToCFG.pdf

answered by Boss (18.3k points)
edited
+3

nice explanation but i think instead of no prefix it should be no proper prefix.

0

@Arjun if we are given some L and we make it to L' = L$in this case we convert the Language to prefix property so in this case all RL will be accepted by DPDA with Empty Stack mechanism? here is a link thats says All RL are accepted by DPDA with empty stack http://planetmath.org/sites/default/files/texpdf/41787.pdf 0 NPDA which accepts by final state there is an equivalent NPDA (equivalent means that accepts the same language) which accepts by empty stack and vice-verse. I agree with this point . But plz anyone show me one NPDA which accepts regular language using empty stack mechanism. 0 Being a deterministic PDA, once the stack becomes empty, the DPDA accepts and halts. So, in no way can a DPDA accepts ww and its prefix. And what in case of NPDA?? Can someone make it more clear? +2 In DPDA, when the stack becomes empty but we still have some character left to be scanned from the input. Then why we can't have steps like this (a,$\epsilon$, anything). // a is scanned from the input and stack is empty. For NPDA in the given pdf link. We define the acceptance by empty stack like this. {w : (q0, w, Z0) ∗ ` (q,$\epsilon$,$\epsilon\$)}.

From this, it is clear that everything from the input is scanned.

+3
Due to the "definition" of acceptance by "empty stack"
0

@Bikram sir

Nevertheless, any regular language can be accepted by a DPDA on empty

stack, and any language accepted by a DPDA on final state is unambiguous,

http://planetmath.org/sites/default/files/texpdf/41787.pdf

But, a* cannot surely be accepted by DPDA by empty stack method since it doesnot have prefix property.

Can you please through some light on this !

I thought of something:(May not be correct)

Any regular lang eg: a* can be converted to a form where it satisfies prefix property.

eg : a* = Ɛ U a U  aa U aaa U aaaa U ...

Now, each of Ɛ,a,aa,aaa,.. can be accepted by a DPDA  by empty stack since each satisfy prefix property.

Ok , now I am struck here, DPDA is not closed under union :(

+1
@vs    satisfying prefix property means, the prefix should not be part of the language. u have misinterpreted.
0
....
0
@arjun sir,

Please provide examples on prefix property
0
Beautiful
0
can someone please share the DPDA for 0* using FINAL STATE.
Answer:

+14 votes
3 answers
1
+21 votes
3 answers
2
+5 votes
2 answers
3
+14 votes
3 answers
4
+16 votes
2 answers
5
+16 votes
4 answers
6
+16 votes
1 answer
7