The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
76 views

Referring to the question https://gateoverflow.in/227957/self-doubt

If the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular language? 

asked in Theory of Computation by Active (3.3k points) | 76 views
0
For which 100 strings you create FA? i.e., We don't know the strings right?

If you didn't get this, let make FA such that " the TM accepts exactly 2 strings "
+1
So the question basically means the TM accepts 100 strings which nobody else knows except the TM itself?
+1
yes... those strings we don't know therefore we can't make FA

1 Answer

0 votes
Best answer
In turing machine the problem of accepting the string is a membership problem in TM ie either the TM will halt or not we dont know therefore the problem comes under the semi decidable problem again we got halting problem and the string is finite therefore we can say it as semi decidable only
answered by Junior (703 points)
selected by

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
49,534 questions
54,122 answers
187,321 comments
71,040 users