0 votes 0 votes Answer with explanation will be acknowledged. Theory of Computation context-free-language theory-of-computation + – Subham Nagar asked Apr 13, 2018 Subham Nagar 534 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 1 votes 1 votes 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. Deepak Poonia answered Apr 13, 2018 • selected Apr 14, 2018 by Subham Nagar Deepak Poonia comment Share Follow See all 4 Comments See all 4 4 Comments reply srestha commented Apr 13, 2018 reply Follow Share 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? 0 votes 0 votes Deepak Poonia commented Apr 13, 2018 i edited by Deepak Poonia Apr 13, 2018 reply Follow Share 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. 1 votes 1 votes srestha commented Apr 13, 2018 reply Follow Share yes got first one reference:https://gateoverflow.in/54718/inherently-ambiguous-languages-deterministic-context-grammars but what do u mean by prefix free? I havenot got that point can u elaborate? 0 votes 0 votes Deepak Poonia commented Apr 13, 2018 reply Follow Share 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. 0 votes 0 votes Please log in or register to add a comment.