Log In
6 votes

in Theory of Computation 1.1k views
Can anyone give examples to prove above points correct or wrong ?

1 Answer

9 votes
Best answer

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

0 votes
0 answers
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
asked Jan 22, 2019 in Theory of Computation Nandkishor3939 139 views
2 votes
3 answers
Given that: { A^m B^n C^k/ if (k=even) then m=n} { A^m B^n C^k/ if (n=even) then m=k} Which of the above languages are DCFL? According to me it is CFL as we have to first count k and then compare other inputs.. same for second language but ... given is both are DCFL? it is only possible if skip path is exists here? does it exist for DCFLs? so confused please guide me? if given answer is correct?
asked Jan 3, 2019 in Theory of Computation S Ram 688 views
1 vote
1 answer
$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 : I think both not DCFL, but need valid reason for it
asked Nov 26, 2018 in Theory of Computation srestha 192 views
0 votes
0 answers
Consider the following languages : L1: {a bn a2n | n β‰₯ 0 } L2: { a a bn a3n | n β‰₯ 0 } Which of the following is true ? A. L1 U L2 is regular B. L1 U L2 is DCFL C. L1 intersection L2 is non regular D. L1 U L2 is not CFL
asked Sep 11, 2018 in Theory of Computation Na462 211 views