edited by
5,452 views
26 votes
26 votes

Let $L_1$ be a recursive language, and let $L_2$ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

  1. $L_1$' is recursive and $L_2$' is recursively enumerable
  2. $L_1$' is recursive and $L_2$' is not recursively enumerable
  3. $L_1$' and $L_2$' are recursively enumerable
  4. $L_1$' is recursively enumerable and $L_2$' is recursive
edited by

2 Answers

Best answer
41 votes
41 votes

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

$L_2$ being recursively enumerable but not recursive means TM for $L_2$ can accept all words in $L_2$ but cannot reject all words not in $L_2 \Rightarrow$ TM for $L_2$' cannot exist (as otherwise TM for $L_2$ could simulate the moves of that TM to reject words in $L_2$')  $\Rightarrow L_2$' is not recursively enumerable. So, (B). 

edited by
11 votes
11 votes

as we know recursive language are closed under complementation hence L1 is recusrive language so L1' also and it is also  recusrive enumerable language
( all options are still open as all satisfy above property )

recursive enumerable language are not closed under complementation so it may be recursive enumerable language or not 
case 1: if L' is  recursive enumerable language
as we know if L and L' are recursive enumerable languages then L is recursive language but here in question they mentioned L2 is not recusrive 
hence L2' cant be recursive enumerable language
therfore L2' accept only case 2 which is L2' is not recursive enumerable language

Ans is B 


 

Answer:

Related questions

26 votes
26 votes
3 answers
4