1,517 views
0 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 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.

Position:
Show:

Related questions

3 3 votes
2 answers 2 answers
11.3k
11.3k views
iarnav asked Oct 27, 2017
11,294 views
We know, Recursive Enumerable Language is not closed under complement. a) So, let's say Y is a R.E language and recursive, then what would be Y' (Y complement)?b) Again Y...
1 1 vote
2 2 answers
4.1k
4.1k views
sh!va asked Jul 12, 2016
4,120 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 3 votes
1 1 answer
2.9k
2.9k views
codingo1234 asked Aug 20, 2017
2,941 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 above
25 25 votes
1 answers 1 answer
8.6k
8.6k views
Vikrant Singh asked Jan 27, 2015
8,612 views
Which of the following languages are Recursively Enumerable language?$\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which...