in Theory of Computation retagged by
3,705 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
in Theory of Computation retagged by
3.7k views

4 Comments

@Ayush Upadhyaya

u mean DCFG and DCFL both unambiguous

right?

then why not C) is answer of this question?

0
0

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

0
0

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.

0
0

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$

1 comment

@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

0
0
Answer:

Related questions