375 views

1 Answer

2 votes
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.

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
140 views
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
141 views
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
148 views
How is equality problem for DCFL decidable?