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?

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

2 Answers 2

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Dec 11, 2014 at 22:38
  • 13
    $\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
    Commented Dec 11, 2014 at 23:31
  • 1
    $\begingroup$ @RickyDemer Please just edit the post! $\endgroup$
    – David Richerby
    Commented Dec 11, 2014 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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