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?
$\begingroup$
$\endgroup$
11
-
$\begingroup$ Ah, you mean, given a regular language $L$ on $\{0\}$, is the corresponding language over $\{0,1\}$ also regular? $\endgroup$– Thomas AndrewsMay 27, 2016 at 16:00
-
$\begingroup$ @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? $\endgroup$– PavelMay 27, 2016 at 16:02
-
$\begingroup$ 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. $\endgroup$– MJDMay 27, 2016 at 16:02
-
$\begingroup$ @MJD what theorem? Can you provide a link, please? $\endgroup$– PavelMay 27, 2016 at 16:03
-
$\begingroup$ 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\}$. $\endgroup$– Thomas AndrewsMay 27, 2016 at 16:04
|
Show 6 more comments
1 Answer
$\begingroup$
$\endgroup$
7
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$.
answered May 27, 2016 at 16:37
-
$\begingroup$ 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. $\endgroup$– PavelMay 27, 2016 at 17:04
-
-
$\begingroup$ The $2q$ I also understand, but not the intersection thing.. $\endgroup$– PavelMay 27, 2016 at 17:07
-
$\begingroup$ 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\}$. $\endgroup$ May 27, 2016 at 17:37
-
$\begingroup$ Thanks. What is $L_{k,r}$ did you mean to put n there instead of r? $\endgroup$– PavelMay 27, 2016 at 17:56