86 views

Answer with explanation will be acknowledged.

| 86 views

+1 vote

Answer : None. No Option is correct.

1. True. All DCFL languages are Unambiguous i.e. There exists at least one Unambiguous grammar for All DCFL languages.

https://gateoverflow.in/54718/inherently-ambiguous-languages-deterministic-context-grammars

2. False. Unambiguous CFG may generate CFL but not DCFL.

3. True. Can be seen from Chomsky Hierarchy.

by Boss (27.9k points)
selected
0
1) False. because suppose a grammar like

$S\rightarrow aS|Sa|a|\epsilon$

It is a DCFL and also an ambiguous grammar.

2)False because

$S\rightarrow aS|a$ generating DCFL. But how do we confirm it is accepted by empty stack mechanism?

Stack might not require for regular language, which is also DCFL.

right?
+1

For ALL RE languages except $\phi$, there exists at least one Ambiguous Grammar. That doesn't mean that ALL RE languages are inherently ambiguous. For a language You have given an ambiguous grammar which doesn't mean that there is no unambiguous grammar.

Truly for DCFL's, Acceptance by empty stack and acceptance by final state are not equivalent for the deterministic pushdown automaton (although they are for the non-deterministic pushdown automaton). The languages accepted by empty stack are those languages that are accepted by final state and are prefix-free :  no word in the language is the prefix of another word in the language.The usual acceptance criterion is final state, and it is this acceptance criterion which is used to define the DCFLs. So, this one reason why Option 2 is False but There is another Reason which I have mentioned in the answer.

0

yes got first one

but what do u mean by prefix free? I havenot got that point

can u elaborate?

0

Prefix-free or Prefix Property for  Any set is Defined as :  No word in the language is the prefix of another word in the language.