# Answer to Question #37941 in Other Math for Sujata Roy

Question #37941

Nobody knows yet if P = NP. Consider the language L defined as

follows

L=(0 + 1)* if P=NP

L= φ otherwise

Which of the following statements is true?

(A) L is recursive

(B) L is recursively enumerable but not recursive

(C) L is not recursively enumerable

(D) Whether L is recursive or not will be known after we find out if P = NP

follows

L=(0 + 1)* if P=NP

L= φ otherwise

Which of the following statements is true?

(A) L is recursive

(B) L is recursively enumerable but not recursive

(C) L is not recursively enumerable

(D) Whether L is recursive or not will be known after we find out if P = NP

Expert's answer

Regular language is a formal language that can be expressed using a regular expression.

A formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

All regular, context-free and context-sensitive languages are recursive.

Incidentally, the all recursive languages are also recursively enumerable.

The right answer is A)

A formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

All regular, context-free and context-sensitive languages are recursive.

Incidentally, the all recursive languages are also recursively enumerable.

The right answer is A)

Need a fast expert's response?

Submit orderand get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

## Comments

## Leave a comment