retagged by
286 views
0 votes
0 votes
All $P$, $NP$ and $NPC$ problems are turing decidable problems. $CFLs$ are in $NP$ area and $CFL's$ are not closed under intersection and complementation. So does it mean that $CFL's$ are undecidable under intersection and complementation. If $CFL$ is undecidable on intersection and complementation then how $NP$ problems can be turing decidable?
retagged by

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
3
srestha asked Dec 12, 2018
421 views
Which one is True?$1)$ A set $S$ , some of it’s elements creates injective function. Then S is decidable$2)$ A bijective function can be $NP$ Hard$3)$ A function which...
0 votes
0 votes
0 answers
4
Mk Utkarsh asked Sep 15, 2018
570 views
A Turing Machine accepts a language if its DCFL but rejects if it's a non deterministic CFL