The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+26 votes

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?

- $L_1 = L_2$
- $L_1 \supset L_2$
- $L_1 \subset L_2$
- None

+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

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.

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.

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

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 488
- Exam Queries 436
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,204 questions

43,662 answers

124,117 comments

42,948 users