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
1
Expert's answer
2013-12-25T04:30:14-0500
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)
Numbers and figures are an essential part of our world, necessary for almost everything we do every day. As important…
APPROVED BY CLIENTS
"assignmentexpert.com" is professional group of people in Math subjects! They did assignments in very high level of mathematical modelling in the best quality. Thanks a lot
Comments
Leave a comment