The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+26 votes
2.3k 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 in Theory of Computation by Loyal (6.1k points)
retagged by | 2.3k views
+2
if it is ask about dpda the B will be answer

1 Answer

+49 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 (17.8k points)
edited by
+2

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 :( 

0
@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


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

34,780 questions
41,755 answers
118,922 comments
41,399 users