18,917 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

if it is ask about dpda the B will be answer

### Subscribe to GO Classes for GATE CSE 2022

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^*$.

by
513 804 798

can someone please share the DPDA for 0* using FINAL STATE.
Made easy provided ans as B. Mailed them also..no reply.. Arjun sir is right, we should never trust these test series.. :)

even there are several wrong answers and for each question either i have to search in GO or post them myself..!

Made Easy never replies to anything at all. :P

1
2,870 views