390 views
0 votes
0 votes

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? 

1 Answer

Best answer
0 votes
0 votes
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
selected by

Related questions

0 votes
0 votes
0 answers
3
admin asked Oct 15, 2019
210 views
Let $ALL_{DFA} = \{ \langle{ A }\rangle \mid A \text{ is a DFA and}\: L(A) = \Sigma^{\ast}\}.$ Show that $ALL_{DFA}$ is decidable.