retagged by
21,848 views
57 votes
57 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
retagged by

1 Answer

Best answer
119 votes
119 votes

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

Related questions

28 votes
28 votes
4 answers
1
Kathleen asked Sep 23, 2014
4,042 views
Given that $A$ is regular and $(A \cup B)$ is regular, does it follow that $B$ is necessarily regular? Justify your answer.Given two finite automata $M1, M2$, outline an ...
34 votes
34 votes
2 answers
2
Kathleen asked Sep 23, 2014
5,009 views
Show that the language $$L = \left\{ xcx \mid x \in \left\{0,1\right\}^* \text{ and }c\text{ is a terminal symbol}\right\}$$ is not context free. $c$ is not $0$ or $1$.
29 votes
29 votes
2 answers
3
Kathleen asked Sep 23, 2014
11,466 views
If $L1$ is context free language and $L2$ is a regular language which of the following is/are false?$L1-L2$ is not context free$L1 \cap L2$ is context free$\sim L1$ is co...
53 votes
53 votes
3 answers
4
Kathleen asked Sep 23, 2014
14,044 views
For the schedule given below, which of the following is correct:$$\begin{array}{ll} \text{1} & \text{Read A} & \text{} \\ \text{2} & \text{} & \text{Read B} \\ \text{3...