edited by
867 views

3 Answers

Best answer
3 votes
3 votes

Answer : B


1. $L = \left \{ <M>| M\,\,\, is\,\,\, a\,\,\, DFA \,\,\,and\,\,\, M\,\,\, accepts\,\,\, 0001 \right \}$

This is very much Decidable, Hence, RE. Just Run $DFA\,\,M$ on the input string $0001.$

"Informally and intuitively," We can design a Halting TM $T$ which will take as input $M$ and run it on string $0001,$ and will definitely Halt because $DFA\,\,M$ will definitely Halt and say Yes if $M$ accepts $0001$ Or it will definitely say No if $M$ does not accept $0001.$

Note that $M$ accepts  string $0001$ doesn't mean that $L(M) = $ {$0001$}


2. $L = \left \{ <M>| M\,\,\, is\,\,\, a\,\,\, TM \,\,\,and\,\,\, M\,\,\, accepts\,\,\, 1000 \right \}$

$M$ is a TM, so, $L(M)$ is a RE language. And Property $P : String\,\,\, 1000\,\,\, belongs\,\,\, to\,\,\, RE$ is a Non-trivial and  Monotone property. 

(A property $P$ of languages is monotone (w.r.t $RE$ languages) if for all RE sets $A$ and $B$, whenever $A ⊆ B$ and $P(A),$ we have $P(B).$ In Other Words, $P$ is monotone if whenever a set has the property, then all supersets of that set have it as well.)

Because of Non-trivial property, It is Undecidable (Not REC) But because of Monotone property, we can't further use Rice's theorem to check Recognizability (That is applicable only for Non-monotone properties of RE languages). So, When these fancy tools don't work for us, We use the basic definition of Recognizability which is that We should be able to Halt and say "Yes" for all the members But we say No or we may not Halt at all for Non-members. 

Here, The members are all the TM $M$ such that $1000 \in L(M).$ So, Since If we have a member $M,$ then we can build a TM $T$ which will run $M$ on $string \,\,1000$ and since $1000 \in L(M),$ $M$ will Halt on $1000$ and say Yes. So, $T$ will Halt and say Yes. But for Non-member $M'$,  $M'$ may not Halt on $string \,\,1000$ and so $T$ can't necessarily say No for all Non-members.

Hence, RE.


3. $L = \left \{ <M>| M\,\,\, is\,\,\, a\,\,\, TM \,\,\,and\,\,\, M\,\,\, accepts\,\,\, 1001\,\,\, but \,\,\,M\,\,\, doesn't\,\,\, accept\,\,\, 1100 \right \}$

We can apply Rice's theorem on this for Decidability as well as recognizability. It is a Non-trivial Property as well as Non-monotone property. $L(T_{Yes} )$ = {$0,11, 1001$} and $L(T_{No} )$ = {$0,11, 1001, 1100$}

Hence, Not-RE.


4. I'll have to read Sipser to know more about this problem. But til then you can make use of the following link :

https://math.stackexchange.com/questions/43276/minimal-turing-machines-are-not-recursively-enumerable-kolmogorov-complexity-i

But It is Not-RE.

selected by
0 votes
0 votes
1) m is DFA m accepts 001 it is decidable you can draw DFA for it which has regular language as 001 is finite so it is RE ,so it is TM recognizable

2)m is TM m accepts 1000 according to rice theorem TM yes ={1000} and TM no ={sigma*} here TM yes is subset of TM no so it should be non RE and hence not Turing recognizable

3)M is TM m accepts 1001 and not 1100 similar to 2 it should not RE hence not Turing recognizable

4)there is no algo for Tm minimisation so not decidable and hence it not RE

I am weak in this topic so please someone check it andPlease correct me if i am wrong

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
0 answers
4