The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+23 votes
2k 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 Boss (6.3k points)
retagged by | 2k views
if it is ask about dpda the B will be answer

1 Answer

+43 votes
Best answer

Answer to the question is (A) L= L2.
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 Veteran (14.6k points)
edited by

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

@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

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.
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?

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.
 

Due to the "definition" of acceptance by "empty stack"

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

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

Please provide examples on prefix property
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

32,693 questions
39,293 answers
110,109 comments
36,701 users