The Gateway to Computer Science Excellence
0 votes
82 views

1.{<M>| M is a TM accepts any string starting with 1}

2.{<M>| M is TM accept exactly 20 strings}

 

Please guide 

I don’t know how to apply rice theorem.

for 1. Is Tyes = { string starting with 1}   Tno = { all strings – strings starting with 1}

  1. what is Tyes and Tno here? I only conclude by intution that when we provide strings as input some got into loop and some got accepts .
in Theory of Computation by Active (2.7k points) | 82 views
0

@Arjun sir ,   @srestha ma'am please help me ,

0
I think , no rice theorem, nedded here

Ans will be decidable

Is ans given?
+1

@Learner_jai the option 2 is decidable as finite number of strings can be accepted by DFA

for option 1. its also decidable since all the strings starting with 1 , can be given by regex 1(0+1)*.

0

@srestha ma'am , question is there in Arjun sir 2nd lecture, I think i need to watch it again, 

 

+1

@srestha

The question is about acceptance of strings by TM. Isn't it a membership problem which is undecidable? 

+1

  (1)Tyes = { string starting with 1}   Tno = { all strings – strings starting with 1} .yes these statements are right ,and we can conclude that this is non trivial property so this is undecidable.

(2) $L_{yes}=${accept exactly 20 strings(0,1,11,111....)  }

$L_{no}=${0} 

so we can clearly see that these two RE set in which first one satisfy the property and second one doesn't ,so we can conclude that this is non trivial property so this is undecidable.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,224 comments
104,909 users