0 votes 0 votes Consider two complementary Languages L and L'. Is it a viable possibility that one of them is in rec and other one in not rec? Theory of Computation theory-of-computation + – shivamrathi1996 asked Aug 24, 2018 edited Aug 24, 2018 by shivamrathi1996 shivamrathi1996 268 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 2 votes 2 votes No, that's not possible since recursive languages are closed under complement. So if $L$ is a recursive language, $L'$ also has to be a recursive language. For proof, see here: https://www.eecs.wsu.edu/~cook/tcs/l19.html goxul answered Aug 24, 2018 selected Aug 25, 2018 by shivamrathi1996 goxul comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes if L is recursive then L' must be recursive because recursive language is closed under complement. BASANT KUMAR answered Aug 24, 2018 BASANT KUMAR comment Share Follow See all 0 reply Please log in or register to add a comment.