Why are (finite word)Büchi sets closed under iterated sums?

Question

For a language recognizable by a DFA, we associate a subset of natural numbers with it. These numbers correspond to the strings accepted by the DFA (consider the binary alphabet, so each word is just representation of a natural number), and we call this set the Büchi set of the regular language (over finite words).

First, we can observe that Büchi sets are closed under addition. That is, if we have two Büchi sets for two regular languages, there exists a third Büchi set, which is the sum of the two sets. The proof is straightforward, as it relies on the closure properties of regular languages under extension, projection, and intersection, and on the fact that bitwise addition, i.e., $( \langle x \rangle , \langle y \rangle , \langle x \rangle + \langle y \rangle )$, is regular.

Now, my question is: why are Büchi sets also closed under iterated sum? By "iterated sum" I mean that instead of adding two elements from two different Büchi sets, we can add multiple elements from the same Büchi set. In other words, the corresponding Büchi set would consist of the numbers that can be reached by summing arbitrary number of elements from one Büchi set.

It seems somewhat similar to Kleene closure (to me), which replaces concatenation with addition. However, this approach doesn't work when I try to prove it. So, I'm curious to know how we can show that Büchi sets are closed under iterated sum.

Answer 1

I hope I understood your question.

Consider an arbitrary $D\subseteq \mathbb N$. Let $D^\#$ be the closure you suggest, i.e., arbitrary sums of elements in $D$, where we assume we may add each element of $D$ several times, as is the case for Kleene closure. Then the set of binary strings $bin(D^\#) \subseteq \{0,1\}^*$ representing these numbers is regular.

The proof is quite similar to the proof of the fact that the Kleene closure $U^*$ of any unary language $U\subseteq \{1\}^*$ is regular.

Take the smallest element $d\in D$. For number $n\in D^\#$ all $n+k{\cdot}d$, $k\in \mathbb N$, are in $D^\#$. In other words, for each residue class $\bmod d$ there is a minimal element that is member of $D^\#$, and from that moment on all elements are in $D^\#$. (Alternatively, the residue class might be empty.)

The set of strings in binary the modulo-value of which is equal to some constant is regular, and so is the set of strings in binary the value of which is at least some number. Regularity of your iterated sum follows by closure under union and intersection.