#Decidability

Question

L={<G> | G is CFG and G is not ambiguous}.Most restrictive set of languages L belongs to is

a) CFL

b) TM decidable

c) TM recognizable

d) not TM recognizable

 

 

Comments

The ambiguity of CFG is not decidable, but in question, it is mentioned that G is not ambiguous. Hence TM accepts CFG with no ambiguity ,so i think it is TM decidable.

Correct me if iam wrong.

---

yeah i feeel the same

---

how TM will check that the grammar is not ambiguous?There is no such algo.So i think this language is not also RE language.

Answer 1

Ambiguity for CFL is Undecidable means if someday , some person name 'CFL' comes to your home and claims that i'm ambiguous or claims that i'm unambiguous then in both cases you have no way to know that whether your new guest name 'CFL' is saying truth or lie.

so it seems like language L is undecidable (not RE).

Comments

If language is undecidable it may / may not be RE
How it is Not RE can you explain please

---

Ambiguity for CFG is RE(Semi decidable) as this problem can be reduced to well known PCP problem.(help of web for proof)

Now if ambiguity for CFG=RE

and as Non-ambiguity for CFG is complement of ambiguity for CFG , if this also RE then eventually both will become REC , so Non ambiguity for CFG must be 'Not RE'.

---

Thanks for help