Question about regular languages

Question

Let $L$ be a regular language over the alphabet $A=\{0\}$. Is it true that the language of binary representations of $n$, such that $0^n\in L$ is regular?

Answer 1

The answer is yes. Let $v(u)$ be the binary value of a binary word $u$. By definition, $$L = \{u \in \{0,1\}^* \mid 0^{v(u)} \in R\},$$ where $R$ is some regular language. First of all, since $R$ is regular, $S = R \cap 0^*$ is also regular and $$ L = \{u \in \{0,1\}^* \mid 0^{v(u)} \in S\}. $$ A regular language on the alphabet $\{0\}$ is semilinear, that is, a finite union of languages of the form $\{0^r\}$ some $r \geqslant 0$ or $0^r(0^n)^*$ for some $r, n$ such that $0 \leqslant r < n$. Since regular languages are closed under finite union and since the languages of the form $\{0^r\}$ are clearly regular, the problem boils down to the following question:

Are the languages $L_{r,n} = \{u \in \{0,1\}^* \mid v(u) \equiv r \pmod n\}\ $ regular?

In fact, $L_{r,n}$ is accepted by the following DFA: $$\mathcal{A} = (\{0, \ldots, n-1\}, \cdot, 0, \{r\})$$ where the transitions are given by the rules $$ q\cdot 0 = 2q \pmod n \quad\text{and}\quad q\cdot 1 = 2q + 1 \pmod n. $$ The reason is that, for any binary word $u$, $v(u0) = 2v(u)$ and $v(u1) = 2v(u) + 1$.