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?


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.