Decidability

Question

Ambiguity of DCFL and CFL is decidable or not??

Answer 1

Given a language DCFL it is always unambiguous because as we have no non determinism and we can define the moves of PDA deterministically..

In other terms there exists at least a one DCFG for a given DCFL which is unambiguous ..Hence ambiguity problem for a DCFL is a trivial property as we are able to say 

Given a DCFL it is always unambiguous ..

Hence the ambiguity problem of DCFL is decidable..

As far as CFL is concerned it may be ambiguous or unambiguous..Actually there is a term "inherent ambiguity" which begins from CFL layer..So given a CFL it may be ambiguous or unambiguous..And we have no such definite algorithm which can decide ambiguity of a given CFL..

Hence the ambiguity problem of CFL is undecidable..

Comments

Why we always talk about the amibuity of CFL What about the amibuity of CSL, Recursive language and Recursive enurmerable language.

---

As I said :

Inherent ambiguity begins from CFL layer

So obviously we can CSL and Recursive languages also which are ambiguous ones..Hence the problem of ambiguity is decidable for regular and DCFL language ; for rest of the higher classes it is undecidable.. 

---

Does determinism always guarantee unambiguity ?

---

Provide any standard reference please ..