I'm trying to get a better grasp of computation theory, and have a few questions that I can't seem to find great answers too.

  1. Given language L, which is non-recognizable, is L* context free?

  2. Is P countably infinite, and why?

  3. Are all recognizable languages NP-complete?

  • 2
    $\begingroup$ One question per post, please! $\endgroup$ – David Richerby May 12 '17 at 12:04

1.) Every context free language is decidable. CFL are not unrecognizable. Refer 1

2.) P is countably infinite because P is the class of decision problem that can be solved on a deterministic turing machine in polynomial time. Every turing machine can be thought of as a finite string over some finite alphabets but all possible set of turing machines are countable infinite hence P is also countably infinite.

3.) NP complete languages are recognizable. A NP Complete languages can be found by modifying the halting problem which is just another form of halting problem(NP-Complete). Halting problems are undecidable but recognizable hence all NP-Complete problems are recognizable. Refer 2 fro details.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.