# Question about regular languages [closed]

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?

• Ah, you mean, given a regular language $L$ on $\{0\}$, is the corresponding language over $\{0,1\}$ also regular? May 27, 2016 at 16:00
• @ThomasAndrews L can be any regular language over the alphabet {0}. Let's us make a sequence of all the lengths of strings in L and make a new language by representing that sequence as binary strings, is the new language regular? May 27, 2016 at 16:02
• Yes, because there is a theorem that says that such a language is either finite or else contains all the multiples of some (finite) set of numbers, minus a finite number of exceptions.
– MJD
May 27, 2016 at 16:02
• @MJD what theorem? Can you provide a link, please? May 27, 2016 at 16:03
• It's not clear why the binary representations of any arithmetic progression is regular. @MJD The problem is the OPs question is a bit vague that the new language is meant to be on two characters, $\{0,1\}$. May 27, 2016 at 16:04

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$.
• Can you please explain why you wrote $S=R\cap 0^*$ isn't $S$ the same as $R$? And what does $2q$ in the transition function mean? Also, I don't understand what you mean in the last line. May 27, 2016 at 17:04
• The $2q$ I also understand, but not the intersection thing.. May 27, 2016 at 17:07
• I misread your question and thought that $R$ was a language over $\{0, 1\}$. Of course, it makes no sense to introduce $S$ if $R$ is a language over $\{0\}$. May 27, 2016 at 17:37
• Thanks. What is $L_{k,r}$ did you mean to put n there instead of r? May 27, 2016 at 17:56