Recursive Language Question ? Mentors please tell the approach


#1

L1 is a Recursive Lang. and L2 is Recursively Enumerable but not Recursive. Which one is true?

a) (L1 Complement) is recursive and (L2 Complement) is Recursively Enumerable

b) (L1 Complement) is recursive and (L2 Complement) is not Recursively Enumerable

c) (L1 Complement) is not recursive and (L2 Complement) is not Recursively Enumerable

d) (L1 Complement) is recursive and (L2 Complement) is Recursive


Theory of Computation category
#2

L1 being recursive, we have a TM M for L1 which accepts all words in L1 and rejects all words in L1’. So, this TM also works for L1’ by changing the accept and reject states. Thus L1’ is recursive.

L2 being recursively enumerable but not recursive means TM for L2 can accept all words in L2 but cannot reject all words not in L2 => TM for L2’ cannot exist (as otherwise TM for L2 could simulate the moves of that TM to reject words in L2’)=> L2’ is not recursively enumerable. So, (B).