Which of the following statement(s) is/are FALSE? (i) There exists a recursively enumerable language whose complement is not recursively enumerable. (ii) If a language L is recursive, then its complement is NOT recursive.
Which of the following statement(s) is/are FALSE? (i) There exists a recursively enumerable language whose complement is not recursively enumerable. (ii) If a language L is recursive, then its complement is NOT recursive. Correct Answer Only (ii)
The correct answer is option 3.
Concept:
Option i: There exists a recursively enumerable language whose complement is not recursively enumerable.
True, Recursive enumerable languages are not closed under complementation. Recursive enumerable is may or may not be closed with respect to string.
Hence there exists a recursively enumerable language whose complement is not recursively enumerable.
option ii: If a language L is recursive, then its complement is NOT recursive.
False, The complement of a recursive language is recursive. If a language L and its complement are Recursive, then L is recursive. Hence If a language L is recursive, then its complement is NOT recursive.
Hence the correct answer is Only (ii).
Additional Information
| Regular | DCFL | CFL | CSL | Recursive | REL | |
| Union | Y | N | Y | Y | Y | Y |
| Intersection | Y | N | N | Y | Y | Y |
| Complement | Y | Y | N | Y | Y | N |
| Difference | Y | N | N | Y | Y | N |
| Prefix | Y | Y | Y | Y | Y | Y |
| Suffix | Y | Y | Y | Y | Y | Y |
| Substring | Y | Y | Y | Y | Y | Y |
| Concatenation | Y | N | Y | Y | Y | Y |
| Reversal | Y | N | Y | Y | Y | Y |
| Kleen closure | Y | N | Y | Y | Y | Y |
| positive closure | Y | N | Y | Y | Y | Y |
| subset | N | N | N | N | N | N |
| substitution | Y | N | Y | N | N | Y |
| Homomorphism | Y | N | Y | N | N | Y |
| Inverse Homomorphism | Y | Y | Y | Y | Y | Y |
|
Y = Closed N = Not closed |
||||||
