TIFR CSE 2016 | Part B | Question: 8

Question

Consider the following language

$$\mathsf{PRIMES} = \Biggl\{ \underbrace{111 \dots 11}_{p \: \text{ times} } : \: p \: \text{ is prime } \Biggl\}$$

Then, which of the following is TRUE?

• A. $\mathsf{PRIMES}$ is regular
• B. $\mathsf{PRIMES}$ is undecidable
• C. $\mathsf{PRIMES}$ is decidable in polynomial time
• D. $\mathsf{PRIMES}$ is context free but not regular
• E. $\mathsf{PRIMES}$ is NP-complete and P $\neq$ NP

Answer 1

The language is $\{1^p \ | \ p \ is \ prime\}$, which is wel-known to be CSL.

Option C