7
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ Well 0* is regular, so we can create a DFA for it. Since $A_{DFA}$ is decidable, 0* is decidable. $\endgroup$ – Ryan Dec 11 '14 at 23:26
  • 5
    $\begingroup$ $0^* \neq 0^\omega$. Only the latter contains infinite strings. $\endgroup$ – Bakuriu Dec 12 '14 at 10:14
  • 1
    $\begingroup$ And that is the trap I fell into - mistaking an infinite number of words with words of infinite length ;) $\endgroup$ – 3yakuya Dec 12 '14 at 16:57
22
$\begingroup$

$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$.

$\endgroup$
  • $\begingroup$ So knowing I accept only 0* I could "go through" the whole input and just assure no other symbol than 0 appears, and when I reach blank symbol (meaning empy piece of the tape is reached) I accept? $\endgroup$ – 3yakuya Dec 11 '14 at 22:38
  • 12
    $\begingroup$ Yes. You misunderstood what $0^*$ means. It does not mean "infinite string of $0$'s". It means "the set of all finite strings of $0$'s". This set does not contain any infinite strings. $\endgroup$ – Andrej Bauer Dec 11 '14 at 23:31
  • 1
    $\begingroup$ @RickyDemer Please just edit the post! $\endgroup$ – David Richerby Dec 11 '14 at 23:44
10
$\begingroup$

The kleene star of a language $L$ is defined as \begin{align} L^\star = \{ w \mid w = \epsilon \text{ or } w = w_1\circ w_2 \circ \ldots \circ w_k, \text{ where } w_i \in L \text{ and } k \in \mathbb{N} \}. \end{align} Thus there is no such thing as an infinite string of $0$'s in the language $0^\star$, only strings of zeros of arbitrary length.

We can easily construct an DFA that accepts the language $A$: it has only one state $s$, which is both start and end state, and one transition $(s, 0) \mapsto s$. Therefore the language $A$ is regular and also decidable.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.