DECIDABILITY

Question

1. L = {<M> | L(M) = {1}}

2. L = {<M> | L(M) is {} }

3. L = {<M> | L(M) has exactly 100 strings}        which are REC R E BUT not REC , NOT EVEN RE

Comments

we can have Tyes as {1} Tno as {0,1}. Tyes is a subset of Tno.

---

{<M> | L(M) has exactly 100 strings}

explain

---

Abhishek Kumar 16 Rice's second theorem can be applied here. So NOT Recursively enumerable.

Answer 1

We can say a language is not even recursively enumerable if we can comeup with atleast one $T_{yes}$and $T_{no }$such that $T_{yes} \subset T_{no }$

1)in first one  $T_{yes} $ = {1}

 $T_{no} $={1,11,111...} So it is not RE

2) In second $T_{yes} $ = {}

 $T_{no} $={1,11,111...} So it is not RE

3)

In third   $T_{yes} $ = {1,10,100,......,.....100times} now you can come with atleast one  $T_{no} $ such that if $T_{yes} \subset T_{no}$ then it is not RE

 $T_{no1} $={1} So it is not RE

$T_{no2} $={1,10,100,......102 times}

$T_{no3} $=${\sum} ^{*}$

Comments

@Prince Sindhiya @Utkarsh Joshi  If a language satisfies rice theorem, the language becomes RE or not RE ?       please help…..