Decidability

Question

Need Explaination :

_________________________________________________________________

" Whether L(G) is a regular language? "-It is undecidable

1)question is why is it undecidable?

___________________________________________________________________

" Whether L(G) is a CFL? (trivial) "- it is decidable

2)question is why is it decidable?

Comments

are you using TM to decide the language?How can you determine a type or property of a language as you have given in 2nd one?

Answer 1

See, First You must describe "What is $G$?"

If $G$ is any Type-0 Grammar, then Both Problems i.e. Deciding whether $L(G)$ is CFL or Regular are Undecidable.

If $G$ is any Type-1 Grammar, then also Both Problems i.e. Deciding whether $L(G)$ is CFL or Regular are Undecidable.

If $G$ is any Type-2 Grammar, then Problem First i.e. Deciding whether $L(G)$  is Regular is Undecidable. But Deciding Whether $L(G)$ is CFL is Decidable (Trivial Since Every Type-2 Grammar always generates a CFL But may or may not generate a Regular language)

If $G$ is any Type-3 Grammar, then Both Problems i.e. Deciding whether $L(G)$ is CFL or Regular are Decidable.

So, It Very much depends on the Domain on/in which you're asking the Problems.

---

Coming to Why Deciding Whether $L(G)$ is Regular or CFL is Undecidable When $G$ is any Type-0 Grammar ?

It's because of Rice's Theorem. Since these are Non-trivial Properties for RE languages.  

Comments

Typo in "Every Type-1 Grammar always generates a CFL"

Also, the undecidability is not due to Rice's theorem. Rather Rice's theorem just proves the undecidability. Also, for Type 1 Grammar this is not applicable.

---

 Typo in "Every Type-1 Grammar always generates a CFL"

Thank you. Corrected. 

 the undecidability is not due to Rice's theorem.

 I did not say that Undecidability is due to Rice's theorem. Only when $G$ is a Type-0 Grammar, Or $M$ is a TM,  Rice's theorem comes into picture.

for Type 1 Grammar this is not applicable.

Yes. Agreed. Rice's theorem is not applicable when $G$ is Type-1 Grammar. Above answer doesn't say Otherwise.

---

According to question does it depend on domain or not , that we cannot say

it is end line of a proof, that I want some elaboration on concept

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

chk here(no domain mentioned)

---

chk here(no domain mentioned)

Domain is always mentioned. Here also, Domain is mentioned. For example, When you see the First row (Regular Grammar) and the 2nd last column ($L(G)$ is Regular)... They combinedly mean that If $G$ is a Regular Grammar, then deciding whether $L(G)$ is Regular or not is Decidable. 

For example, When you see 4th Row (Context sensitive Grammar) and same 2nd last column ($L(G)$ is Regular) ..They combinedly mean that If $G$ is a Context sensitive Grammar, then deciding whether $L(G)$ is Regular or not is Undecidable. 

---

Let me give elaborate this domain thing with a small example :

We say that Halting Problem is Undecidable.... Right?? 

Yes, We say this statement lots of times. But This is not a complete statement. It could be wrong as well. How??

See, When I say "Halting Problem of TM is Undecidable" .. It is absolutely correct.

But What if I say "Halting Problem of HTM is Undecidable" .... Now it is False. Because Halting Problem of HTM(Halting TM) is always Decidable.

So, This is the effect of Domain.

Here, "Whether Halting Problem is decidable or not" is the Problem and TM(Or HTM) is the domain.