NIELIT 2017 July Scientist B (CS) - Section B: 59

Question

Let $L$ be a language and $L’$ be its complement. Which one of the following is NOT a viable possibility?

• A. Neither $L$ nor $L’$ is RE.
• B. One of the $L$ and $L’$ is RE but not recursive;the other is not RE.
• C. Both $L$ and $L’$ are RE but not recursive.
• D. Both $L$ and $L’$ are recursive.

Comments

Option $(C)$

https://gateoverflow.in/1810/gate2014-1-35

Answer 1

Answer: C

http://www.geeksforgeeks.org/gate-gate-cs-2014-set-1-question-45/

https://gateoverflow.in/1810/gate2014-1-35

Answer 2

If both L and L’ are recursively enumerable, then L must be recursive. Hence, both L and L´ are recursively enumerable, but not recursive is not a viable possibility.

Answer 3

option C

bcz RE language are not closed under complementation.

Answer 4

opt a is viable according to the statement.

opt b is also viable because if L1 is recursive enumerable then comp(L1) should not be in recursive language and vice versa.

opt c is viable recursive enumerable is not closed under complementation.

opt d is not viable because recursive holds complementation rule.

Answer:opt d