L is recursive means TM for L accepts all words in L and rejects all words not in L.So, just by changing the accept to reject and vice verse we get a TM for L'. Thus L' must also be recursive.

The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+19 votes

Which of the following is true?

- The complement of a recursive language is recursive
- The complement of a recursively enumerable language is recursively enumerable
- The complement of a recursive language is either recursive or recursively enumerable
- The complement of a context-free language is context-free

+19 votes

+5

L is recursive means TM for L accepts all words in L and rejects all words not in L.So, just by changing the accept to reject and vice verse we get a TM for L'. Thus L' must also be recursive.

+2 votes

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 411
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,786 questions

41,762 answers

118,950 comments

41,409 users