3
$\begingroup$

Write $\bar n$ for the decimal expansion of $n$ (with no leading 0). For a set $S$ of natural numbers, let its set of expansions (in base 10) be $\bar S = \{\bar n \mid n \in S\}$. Is there a nice characterization of the sets $S$ such that $\bar S$ is a regular language?

Obviously adding or removing a finite number of values doesn't affect the regularity of $\bar S$, so what matters is only the “asymptotic” behavior of $S$, i.e. what it looks like above a certain threshold.

For numbers written in unary, there's a simple characterization: the corresponding set of representations is regular iff the set is ultimately periodic (i.e. it's of the form $\{a n + b \mid n \in \mathbb{N}, b \in F\}$ for some finite set $F$ and some constant $a$). An ultimately periodic set's set of expansions is a regular language: it's a finite union of images of affine functions, which are regular. There are other sets whose set of expansions is regular, such as $\{10^n \mid n \in \mathbb{N}\}$. On the other hand, the set of squares doesn't have a regular set of expansions.

In general, how can $S$ look like when $\bar S$ is regular? Is there a simple arithmetic characterization of sets whose sets of expansions is regular?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.