# Sets whose decimal expansions form a regular language

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?

• Might still be the same answer (iff $S$ is ultimately periodic)? Looks closely related: en.wikipedia.org/wiki/Automatic_sequence, en.wikipedia.org/wiki/B%C3%BCchi_arithmetic, en.wikipedia.org/wiki/…, but I haven't dug through that and work out what it implies for your question.
– D.W.
Nov 17, 2017 at 22:24
• @D.W. You can recognize powers of 10 (but not, say, powers of 2) in base 10 with a finite automaton. Nov 17, 2017 at 22:26
• Oh, right. Good point. Thanks for the correction.
– D.W.
Nov 17, 2017 at 22:28
• On second thoughts there doesn't seem to be a nice characterizations. What's nice about the numbers that contain a 3 when written out in decimal? Nov 18, 2017 at 0:05