Problem Detail: I found a statement (without explanation) that a language $A = 0^*$ is decidable. How is that possible? I mean, how would we build a Turing machine that would accept (or reject) a possibly infinite string of 0’s? I also thought that maybe we could create an enumerator that would create all words from $0^*$ with increasing length, but I am not sure if we can. So is $0^*$ a decidable language? And if so, why?
Asked By : 3yakuya
Answered By : Jake
$0^*$ is the set of finite strings consisting only of $0$. There are no possibly infinite strings in $0^*$. It is trivially regular because the regex $0^*$ accepts exactly $A$ by definition. All regular problems are computable so we can definitely create a Turing machine for it (look up NFA’s and DFA’s for more info on the connection of Turing machines to regular languages). This is just a confusion in what is meant by Kleene closure. If you look here you can see that it is the union of all strings of length 1, 2, 3, … and so on for all natural numbers. Infinity is not a natural number so there are no strings of infinite length in $A$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/35155
