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?

  • $\begingroup$ 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. $\endgroup$ – D.W. Nov 17 '17 at 22:24
  • $\begingroup$ @D.W. You can recognize powers of 10 (but not, say, powers of 2) in base 10 with a finite automaton. $\endgroup$ – Gilles Nov 17 '17 at 22:26
  • $\begingroup$ Oh, right. Good point. Thanks for the correction. $\endgroup$ – D.W. Nov 17 '17 at 22:28
  • $\begingroup$ 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? $\endgroup$ – Gilles Nov 18 '17 at 0:05

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.