The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
63 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) | 63 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 (493 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

44,511 questions
49,969 answers
165,837 comments
65,915 users