# DCFL,AMBIGUITY

1.1k views

0
Can anyone give examples to prove above points correct or wrong ?
0

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

## Related questions

1
139 views
the answer is given that the statement 2 is correct? But how… even if we create a DCFL by final state condition like : q(b,z0| z0)-→ final state ,q(null,a|z0) ----→ final state [Thats what was mentioned in the video solution] it will accept the string aab
$L_{1}=\left \{ 0^{m}.1^{n}.2^{m}.3^{n} \right |n,m>0\}$ $L_{2}=\left \{ a^{i}.b^{j}.c^{k}.d^{l} \right |i+k=j+l\}$ which one DCFL? Refrence :https://gateoverflow.in/15327/context-free-or-not I think both not DCFL, but need valid reason for it