Question #38612
Nobody knows yet if P = NP. Consider the language L defined as follows:
L=(0+1)* if P = NP
And
L=j 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
L=(0+1)* if P = NP
And
L=j 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
Answer on Question#38612 – Math - Other
Regular language is a formal language that can be expressed using a regular expression. A formal language (a set of strings of symbols that may be constrained by rules that are specific to it) 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.
So the right answer is A).
