The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
51 views
Whether a given language is context free or not? Is it decidable or undecidable? Please explain in detial.
asked in Theory of Computation by Junior (561 points) | 51 views

1 Answer

+2 votes

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.

answered by Boss (13.2k points)
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....

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

36,157 questions
43,608 answers
123,961 comments
42,860 users