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.2k
- Digital Logic 2k
- Programming & DS 3.7k
- Algorithms 3.2k
- Theory of Computation 4k
- Compiler Design 1.6k
- Databases 3k
- CO & Architecture 2.6k
- Computer Networks 3k
- Non GATE 1k
- Others 1.3k
- Admissions 486
- Exam Queries 435
- Tier 1 Placement Questions 18
- Job Queries 56
- Projects 9

36,157 questions

43,608 answers

123,961 comments

42,860 users