RE or Non RE

Question

1) Language describing the ambiguity of CFG is RE or Non RE?

2) Language describing the non-ambiguity of a CFG (whether a given CFG is non-ambiguous) and complement of the language of ambiguity of CFG are RE or Non RE?

3) Inherent Ambiguity of CFL is RE or Non RE?

4) Is language of the complement of Ambiguity and the language of non-ambiguity  of CFG same?

Comments

1) RE. If there is one grammar which has atleast 2 same parse tree, then it is satisfies yes cases of the grammar.

But for no cases we have to search for infinite number of string to say grammar is not ambiguous. So, no cases making loop to say grammar is not ambiguous.

2) Non ambiguity of a CFG is grammar that are not ambiguous for that perticular grammar.

where as complement of ambiguity of CFG is the grammar that are all grammar other than that grammar.

So, complement of ambiguity of CFG is non RE, as it is for infinite number of grammar.

But non ambiguity or unambiguity of a grammar is REC.

 

3)@Anusha explained it. It is non RE.

4) No, both are not same

 

@Arjun Sir chk now

---

I think all four auestions are same. It is ambiguity problem. It means to ask ambiguity problem of CFG. And ambiguity problem is undecidable for sure. But partially decidle or not??? @ Arjun sir am I right??? Is it RE for all?

---

No,

all are twisted question.

Try to think them separately

Answer 1

1. is r.e. but not recursive (a bit of google search will get a proof).

2. In my opinion both are the same and not even r.e. due to 1 being r.e. and not recursive. If both are not same then what is the difference?

3. Again should be not r.e. But not having a proof.

4. Yes, otherwise what's the difference?

Comments

Sir, I just thought

non ambiguity= ~(ambiguity)

and

complement of ambiguity=$\Sigma ^{*}$-ambiguity.

yes both same

---

Yes, think about halting problem and its complement. I suppose they ignore invalid inputs (invalid TM descriptions) for these problems.

---

https://cs.stackexchange.com/questions/74650/what-is-the-complement-of-halting-problem

---

Non ambiguity for CFG would be stated like , every string of CFG must have exactly one LMD or RMD or derivation tree.

and complement of ambiguity for CFG would be stated like , Everything other than ambiguity problem for CFG , this also include invalid inputs...like grammar that is  not even context free...