in Theory of Computation retagged by
18,917 views
54 votes
54 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?

  1. $L_1 = L_2$
  2. $L_1 \supset L_2$
  3. $L_1 \subset L_2$
  4. None
in Theory of Computation retagged by
by
48 80 117
18.9k views

2 Comments

if it is ask about dpda the B will be answer
15
15

Subscribe to GO Classes for GATE CSE 2022

1 Answer

107 votes
107 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

edited by
by
513 804 798

5 Comments

can someone please share the DPDA for 0* using FINAL STATE.
0
0
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..!
0
0

Made Easy never replies to anything at all. :P

0
0
Answer:

Related questions