0 * é decidível?

Encontrei uma declaração (sem explicação) de que um idioma $A = 0^*$é decidível. Como isso é possível? Quero dizer, como construiríamos uma máquina de Turing que aceitaria (ou rejeitaria) uma sequência possivelmente infinita de zeros? Eu também pensei que talvez pudéssemos criar um enumerador que criaria todas as palavras de$0^*$ com o aumento do comprimento, mas não tenho certeza se podemos.

Então é $0^*$uma linguagem decidível? E se sim, por quê?

$0^*$ é o conjunto de cadeias finitas consistindo apenas em $0$. Não há seqüências possivelmente infinitas em$0^*$. É trivialmente regular porque o regex$0^*$ aceita exatamente $A$por definição. Todos os problemas regulares são computáveis ​​para que possamos criar definitivamente uma máquina de Turing (consulte NFA e DFA para obter mais informações sobre a conexão de máquinas de Turing a idiomas regulares).

Isso é apenas uma confusão no que se entende por fechamento de Kleene. Se você olhar aqui, poderá ver que é a união de todas as cadeias de comprimento 1, 2, 3, ... e assim por diante para todos os números naturais. O infinito não é um número natural, portanto, não há cadeias de comprimento infinito em$A$.

A estrela kleene de uma língua $L$ é definido como

$$\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}$$ Portanto, não existe uma sequência infinita de $0$está no idioma $0^\star$, apenas cadeias de zeros de comprimento arbitrário.

Podemos construir facilmente um DFA que aceite o idioma $A$: possui apenas um estado $s$, que é o estado inicial e final, e uma transição $(s, 0) \mapsto s$. Portanto, a linguagem$A$ é regular e também decidível.