Decidability

Question

L= {<G> | G is CFG and G is NOT ambiguous} .
L is TM recognizable or not even TM recognizable?

Comments

Determining whether a CFG is ambiguous is undecidable?

---

Yes. ..It is not even semi-decidable. But what about its complement?

---

@Soumya

L1 = {<G> | G is CFG and G is ambiguous}. This is Turing recognizable. Read Arjun sir, answer here.
https://gateoverflow.in/19947/which-of-the-folowing-are-r-e

Compliment of L1 should not be Turing recognizable. Otherwise, both L1 and compliment of L1 become decidable.

---

Thank you :)

---

@Soumya

I think it will be decidable.

L is CFG and not ambiguous

Then it can be CFG or regular grammar

right?

---

@srestha. It's not even RE.
Read this

---

no that question is different I think

That question is about complement of ambiguous grammar directly.

But, ur question is "Is a CFG is decidable or not"

Suppose $S\rightarrow aSb|ab$ or $S\rightarrow aS|\epsilon$

will it not decidable?

---

See the difference

1) wheather L(G) is CFL? is decidable

2)Wheather L(G) is ambiguous ? is undecidable

right?

Do, u think , as CFL is defined on DCFL and not CFL , that is why it is decidable?

Otherwise it will be undecidable?

https://gatecse.in/grammar-decidable-and-undecidable-problems/

---

@srestha..
Both are same. 
L is the set of encoding of ALL such CFG's that are not ambiguous. Not just one. 

---

but

1) wheather L(G) is CFL? is decidable

So,

why not we make a TM

which accepts all unambiguous grammar?

---

@srestha Who told that is decidable?

---

when G is DCFG

here  we find ,"if L(G) is CFL" is decidable

right?

--------------------------------------------------------------------------

My question was

 G is CFG

here when we find ,"if L(G) is CFL" is decidable or not?

-----------------------------------------------------------------------------

Moreover , an ambiguous grammar is undecidable.

Does it mean, an unambiguous grammar also need to be undecidable?

Answer 1

as L is  CFG  it is subset of UG

that is TM recoznigable

Comments

who told $L$ is CFL?