1,007 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

1 Answer

1 votes
1 votes

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

1 votes
1 votes
2 answers
2
sh!va asked Jul 12, 2016
2,978 views
I) Every language in NP is recursive.II)Every language in NP is recursively enumerable.Which of the statements is /are true?A. I onlyB. II onlyC. Both I and IID Neither I...
3 votes
3 votes
1 answer
3
codingo1234 asked Aug 20, 2017
2,208 views
If L1 and L2 are Turing-Recognizable then L1 ∪ L2 will be(a) Decidable(b) Turing-recognizable but may not be decidable(c) May not be Turing recognizable(d) None of abov...