The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

0 votes

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

+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.

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.

- All categories
- General Aptitude 1.3k
- Engineering Mathematics 5.5k
- Digital Logic 2.1k
- Programming & DS 4k
- Algorithms 3.4k
- Theory of Computation 4.2k
- Compiler Design 1.6k
- Databases 3.1k
- CO & Architecture 2.7k
- Computer Networks 3.1k
- Non GATE 1.1k
- Others 1.4k
- Admissions 501
- Exam Queries 450
- Tier 1 Placement Questions 19
- Job Queries 62
- Projects 12

38,106 questions

45,608 answers

132,246 comments

49,232 users