4
$\begingroup$

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

Improve this question
$\endgroup$
1

3 Answers 3

Reset to default
11
$\begingroup$

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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
-2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – András Salamon
    Commented Mar 21, 2014 at 22:31
  • $\begingroup$ 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. $\endgroup$
    – NisaiVloot
    Commented Mar 22, 2014 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.