The Gateway to Computer Science Excellence
0 votes

Answer with explanation will be acknowledged.

in Theory of Computation by Active (1k points) | 80 views

1 Answer

+1 vote
Best answer

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.

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

3. True. Can be seen from Chomsky Hierarchy.

by Boss (26.1k points)
selected by
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.


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.


yes got first one


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

can u elaborate?


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.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,650 questions
56,194 answers
94,864 users