73 views
Whether a given language is context free or not? Is it decidable or undecidable? Please explain in detial.
0

Whether a given language is context free or not? Is it decidable or undecidable?

Undecidable. Given language could be anything... NOT RE or RE but not REC or REC or Regular....anything.

If this problem had been Decidable then we could decide many problems which are already proven to be Undecidable. Like consider this "Given a $TM$ $M$, Whether $L(M)$ is CFL or Not??"...We know, by Rice's theorem, that It is Undecidable.

The problem statement "Given a $TM$ $M$, Whether $L(M)$ is CFL or Not??" is equivalent to saying "Given a RE language $L$, Decide whether $L$ is CFL or Not??" ..Which is Already proven to be Undecidable.

Hence, "Whether a given language is context free or not? " is Undecidable.

0
thanks for the explanation if in statement language is replaced by grammar then it will be decidable na?
+1

if in statement language is replaced by grammar then it will be decidable na?

If we replace "language" word by "grammar" word then the Statement will be " Whether a given Grammar is context free or not?"...Yes. It is Decidable because If I give you any Grammar then to check whether the given grammar is CFG or not, we just need to check One thing and that is : Left hand side of production should have only one variable.  Which is easy and can be done by Algorithm.

NOTE that the above problem is different than the following problem :

"Given a Grammar $G$, finding whether $L(G)$ is CFL or not" .... It is Undecidable and GATE 2018 question as well.

0
thank you for the clarification of statements....

1
2
6