recategorized by
652 views
5 votes
5 votes

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?

  1. $\mathsf{PRIMES}$ is regular
  2. $\mathsf{PRIMES}$ is undecidable
  3. $\mathsf{PRIMES}$ is decidable in polynomial time
  4. $\mathsf{PRIMES}$ is context free but not regular
  5. $\mathsf{PRIMES}$ is NP-complete and P $\neq$ NP
recategorized by

1 Answer

1 votes
1 votes

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

Option C

Answer:

Related questions

3 votes
3 votes
1 answer
1
go_editor asked Dec 28, 2016
609 views
Assume $P \neq NP$. Which of the following is not TRUE?$2$-SAT in NP$2$-SAT in coNP$3$-SAT is polynmial-time reducible to $2$-SAT4-SAT is polynmial-time reducible to $3$-...
3 votes
3 votes
1 answer
2