1 votes 1 votes State whether these languages are recursive ,RE, non RE? L1 = {<M>| M is a TM and |L(M)| ≤ 3}. L2 = {<M>|M is a TM and |L(M)| ≥ 3}. Theory of Computation theory-of-computation recursive-and-recursively-enumerable-languages + – vaishali jhalani asked Dec 15, 2016 • retagged Jul 4, 2017 by Arjun vaishali jhalani 261 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes By Rice Theorem For L2, we can have Tyes = Σ* and Tno = Ф but here we cannot have Tyes and Tno such that L(Tyes)⊂L(Tno). So L2 is not recursive. For L1, we can have Tno = Σ* and Tyes = Ф and here L(Tyes)⊂L(Tno) So L1 is not RE. Gate Mission 1 answered Dec 15, 2016 Gate Mission 1 comment Share Follow See 1 comment See all 1 1 comment reply hacker16 commented Dec 25, 2017 reply Follow Share hey, Gate Mission 1 can you please explain it further 0 votes 0 votes Please log in or register to add a comment.