# Regular languages under change of encoding

Consider a regular language $L$ with alphabet $\Sigma = \{0,1\}$. Can we say that the set of strings in $L$ (representing non-negative integers in binary encoding) when represented in some other encoding (say unary, or, decimal) also form a regular language ?

Formally, is it the case that the language $L' = \{w | w \in 1^*, \exists w' \in L \text{ such that the unary encoding of } w' \text{ is } w \}$ also regular?

What happens when the base is shifted to a lower number? For example can we also say anything about the following language: $L'' = \{w | w \in \{0,1,2\}^*, \exists w' \in L \text{ such that the ternary encoding of } w' \text{ is } w \}$

The answer is no. I'll give an example of a language $L$ which is regular in binary but not in unary:

Consider $L=\{10^k|k\in \mathbb{N}\}$. The corresponding language in unary is $L'=\{1^{2^k}|k\in \mathbb{N}\}$.

It's easy to see that $L$ is regular while $L'$ is not even context free.

L'' also isn't regular either, by the link @Sylvain posted in his comment.

When the base k representation is regular, the set is called k-automatic

The wikipedia article on these reads:

For given "k" and "r", a set is "k"-automatic if and only if it is "k^r"-automatic. Otherwise, for "h"and "k" multiplicatively independent, then a set is both "h"-automatic and "k"-automatic if and only if it is 1-automatic, that is, ultimately periodic.

It mentions other properties as well.

If my memory is right, the answer is yes as a consequence of the following two points:

(1) conversion between two number bases can be expressed by a FS transducer -- not sure about that one, please check;

(2) regular languages are closed under application of a FST -- this follows from the more general fact that FSTs are closed under compositions.

A possible reference for FSTs is the Sakarovitch textbook "Elements of automata theory". Hope this helps...

• For conversion between bases that are relatively prime, presumably you are thinking of an extension of Sakarovitch IV.1.6 (quotient of binary input by 3)? – András Salamon Mar 21 '14 at 22:31
• I think that point (1) works when converting from a base $\beta$ to a base $\chi$ dividing $\beta$ (but different from 1). Indeed, if you have a number of the form $N = \beta q+r$ with $\beta = \chi \pi$, then the conversion follows by observing that $N = \chi q' + r'$ with $r' = r ~mod~ \chi$ and $q' = \pi q + r ~div~ \chi$. Informally, the conversion can be performed digit-by-digit, thus with bounded memory. – NisaiVloot Mar 22 '14 at 0:25