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

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

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

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

CC BY-SA 3.0
2014-03-21T23:32:10.670Z
2014-05-27T08:17:47.890Z
2014-05-27T08:17:47.890Z
R B
<p>When the base k representation is regular, the set is called k-automatic</p>

<p>The wikipedia article on these reads:</p>

<p>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.</p>

<p>It mentions other properties as well.</p>

CC BY-SA 3.0
2014-03-22T00:58:42.067Z
2014-03-22T00:58:42.067Z
JimN
<p>If my memory is right, the answer is yes as a consequence of the following two points:</p>
<p>(1) conversion between two number bases can be expressed by a <a href="http://en.wikipedia.org/wiki/Finite_state_transducer" rel="nofollow noreferrer">FS transducer</a> -- not sure about that one, please check;</p>
<p>(2) regular languages are closed under application of a FST -- this follows from the more general fact that FSTs are closed under compositions.</p>
<p>A possible reference for FSTs is the Sakarovitch textbook &quot;Elements of automata theory&quot;. Hope this helps...</p>

CC BY-SA 3.0
2014-03-21T22:31:47.330Z
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
CC BY-SA 3.0
2014-03-22T00:25:10.720Z
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
CC BY-SA 3.0
2014-03-21T18:50:32.260Z
2014-03-21T18:50:32.260Z
2020-06-17T09:38:08.363Z
NisaiVloot
<p>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 ?</p>

<p>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? </p>

<p>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 \}$</p>

CC BY-SA 3.0
2014-03-22T00:07:05.170Z
See http://cstheory.stackexchange.com/questions/2083/proving-the-set-of-powers-of-2-over-ternary-alphabet-to-be-non-regular for a related question, and Cobham's Theorem.
Sylvain
<fl.formal-languages><automata-theory><regular-language><encoding>
Regular languages under change of encoding
Umang
# Regular languages under change of encoding

(Asked by: username_0 on 2014-03-21)

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 \}$

**Tags:** fl.formal-languages, automata-theory, regular-language, encoding

> **Comments:**
> **username_1**: See http://cstheory.stackexchange.com/questions/2083/proving-the-set-of-powers-of-2-over-ternary-alphabet-to-be-non-regular for a related question, and Cobham's Theorem.  

---

## 3 answers

### Answer by username_2 on 2014-03-21. Score: 11

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 @username_1 posted in his comment.


---

### Answer by username_3 on 2014-03-22. Score: 7

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.


---

### Answer by username_4 on 2014-03-21. Score: -2

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](http://en.wikipedia.org/wiki/Finite_state_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...

> **Comments:**
> **username_5**: 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)?  
> **username_4**: 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.  

---

