GATE Overflow | Mock GATE | Test 1 | Question: 15

Question

Which one of the following statements is not correct?

• A. For non-deterministic push down automata (NPDA), set of all languages accepted by empty stack is always a proper subset of set of all languages accepted by final state
• B. For deterministic push down automata (DPDA), set of all languages accepted by empty stack is always a proper subset of set of all languages accepted by final state
• C. A grammar which generates a DCFL may be ambiguous
• D. A deterministic context free grammar (DCFG) can never be ambiguous

Comments

So, nondeterministic pda accept same set of languages for both empty stack and final state acceptance?

---

I think (d) must be DCFL can never be ambigous and that is true.

---

Yes, @Ayush Upadhyaya DCFL cant be inhererntly ambiguous but DCFG can be ambiguous.

---

DCFG are always unambiguous.So, (D) is true.

---

Any reference?

---

Plz explain the 1,2???

---

What is correct statement of A?

---

Since NPDA is more powerful than DPDA it accepts all sets of CFL and not only proper subsets.

 a language L has an NPDA that accepts by final state if and only if some NPDA accepts it by empty stack.So the correct statement will be,

For deterministic push down automata (DPDA), set of all languages accepted by empty stack is always a proper subset of set of all languages accepted by final state.

 

---

https://gateoverflow.in/135969/dcfls

---

@ Ayush Upadhyaya "DCFG are always unambiguous how this statement is correct,"suppose you are given a NDCFG and you convert it into DCFG,well that does not assure that it is removed ambiguity also,bcoz reason of ambiguity is something else i.e due to precedence and associativity and not non determinism

In option (d) it must DCFL ,right?

---

https://cs.stackexchange.com/questions/102245/can-deterministic-context-free-grammars-be-ambiguous

---

@Ayush Upadhyaya

u mean DCFG and DCFL both unambiguous

right?

then why not C) is answer of this question?

---

@srestha-Option (C) says "A grammar" and not necessarily a DCFG.So, that may be ambiguous.

---

I think the answer is A.

https://gateoverflow.in/377/gate1999-1-6 For NPDA acceptance by empty stack and acceptance by final state is equal not always a proper subset.

https://gateoverflow.in/54718/inherently-ambiguous-languages-deterministic-context-grammars DCFL can be generated by an ambiguous grammer.

Answer 1

$Power:$ $NPDA_{final state} = NPDA_{empty stack} > DPDA_{final state} > DPDA_{empty stack}$

So, Option A is incorrect (Answer).

---

We know that NPDA are more powerful than DPDA. An example of a language that NPDA can accept, but DPDA can't is a $ww^r$.

The expressive power of DPDA is further reduced if we enforce acceptance by empty stack.

 

Suppose our language is $L=\{abc, abcabc\}$ and we create a DPDA for it, which accepts by empty stack. It will be created such that when it sees "abc" the stack is empty, and hence, we accept it.

In such a case, whevever we encounter "abc" we will stop and accept it, which makes it impossible for us to accept "abcabc" as we won't ever look past the initial "abc".

 

By the same logic, even $a^*$ (which is a Regular Language) can't be accepted by a DPDA which accepts with empty stack; which shows how weakly expressive it is.

---

This can be formally described as DPDA can only accept the languages that have prefix property.

A Language is said to have prefix property if for every $w$ $\varepsilon$ $L$, $L$ does not have any proper prefix of $w$

Comments

@JashanArora

can you give some reference to option d .I feel it is also false because,DCFG can be ambiguous.

for example$S->aSb|ab|epsilon$ is a ambiguous DCFG for language$L=epsilon,ab,aabb,aaabbb.......$

.Although, there is a unambiguous grammar $S->aSb|epsilon$ for the same language. but the word never in the statement is making the option d false.

where am i going wrong??

this question also saying the same thing:https://gateoverflow.in/135969/dcfls