in Theory of Computation
1,030 views
0 votes
0 votes
If a language L and its complement L' are recursively enumerable then choose the correct statement

a) L is recursive but not L'

b) Both L and L' are recursive

c) L' is recursive but not in L

d) None of these
in Theory of Computation
1.0k views

4 Comments

edited by
option b is correct both L and L' are recursive.
0
0
you mean b?

and whats the reason??
0
0
because if L and L' are REL than L is recursive and recursive languages are closed under complementation so L' will also be recursive.
0
0
yeah i mean to say b, edited my comment as well.
Given a Language L, and its complement L' is recursive enumerable.
Case 1 : Suppose  L is recursive, and recursive languages  are closed under complementation, so L' is also recursive, now every recursive language is also, recursive enumerable, so we can say its satisfy our condition, which is option b.
Case 2 : Either one of L or L' is not recursive, that means its recursive enumerable, and recursive enumerable lanugages are not closed under complementation, so we can't say for sure that complement is recursive enumerable. This case is not possible.
1
1

1 Answer

1 vote
1 vote

Answer is (b): both L and L' are recursive

Definition of decidable language:

"a language L is decideble iff L is recursive enumerable and L' is also recursive enumerable".

                              or

"a language L' is decidable iff L' is recursive enumerable and L is also recursive enumerable".

So, L and L' are recursive.

Related questions