2,524 views

1 Answer

Best answer
11 votes
11 votes

First statement is wrong..For example we have a grammar corresponding to odd palindromes :

S --> aSa | bSb |  a | b  

which generates a CFL language but not DCFL..[As DPDA for palindrome language is not possible]..However the given grammar is unambiguous and hence the given statement is wrong..

Third statement is also false as class of languages accepted by an empty stack in the case of DPDA is a proper subset of class of languages which are accepted by the final state of a DPDA..So the converse of the statement is not true necessarily..Specifically those DCFL languages which accept by empty stack mechanism possess prefix property while a DCFL languages which accept by final state need not possess it.Hence option C) is wrong as well..

Now coming to second statement which says there is an unambiguous grammar for every DCFL ..This is true because a language is unambiguous iff there is at least one grammar corresponding to it which is unambiguous..As DCFL name itself suggests that there is determinism at each stage of input hence no possibility of a choice..Hence every DCFL contains at least one unambiguous grammar.In fact the language for which there is no unambiguous grammar is known as inherently ambiguous..Inherent ambiguity begins from CFL layer of Chomsky hierarchy.

Hence option B) should be correct option..

selected by

Related questions

1 votes
1 votes
1 answer
1
2 votes
2 votes
0 answers
2
h4kr asked Feb 2, 2023
458 views
Can DCFL be ambiguous?
1 votes
1 votes
2 answers
3
ggwon asked Dec 29, 2022
728 views
L = {$a^{n+m}b^{n}a^{m} | n,m \geq 0$}Is the above language DCFL or CFL ?