retagged by
3,664 views
6 votes
6 votes

Which one of the following statements is not correct?

  1. 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
  2. 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
  3. A grammar which generates a DCFL may be ambiguous
  4. A deterministic context free grammar (DCFG) can never be ambiguous
retagged by

1 Answer

6 votes
6 votes

$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$

Answer:

Related questions