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)
